洛谷OJ: P1064 金明的预算方案(01背包问题)

思路: 这是一道01背包问题, 只有选与不选的这两种情况, 但是这题物品的属性比起普通的01背包只有重量和价值以外多了主件/附件这一属性, 再看题目中"每个主件可以有0个、1个或2个附件"这一句话,一种物品的所有选择情况只有:1.只选择主件  2.选择主件+附件1  3.只选择主件和附件2  4.选择主件和所有附件, 那么我们很容易就能得到状态转移方程dp[i]= max{dp[i], dp[i-w]+v(i>=w), dp[i-w-w1]+v+v1(i>=w+w1), dp[i-w-w2]+v+v2(i>=w+w2), dp[i-w-w1-w2]+v+v1+v2(i>=w+w1+w2) }

/**
 *	题目: 洛谷OJ P1064 金明的预算方案 
 *	题型: 01背包 
 **/
#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 32000+10, maxm = 60+10;
int dp[maxn], dp_max[maxn], k, n, m;
struct Goods{
	int id, v, p;
};
vector<int> p[maxm][2];
vector<Goods> g;

int main()  {
	int t1, t2, t3;
	/************input**************/
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> t1 >> t2 >> t3;
		if(t3) { //如果这是一个附件 
			p[t3][0].push_back(t1); //0储存附件价格 
			p[t3][1].push_back(t2); //1储存附件重要度 
		}
		else {
			k++;
			g.push_back(Goods{i, t1, t2});
		}
	}
	/*******************************/
	for(int i = 0; i < k; i++) {
		for(int j = n; j >= g[i].v; j--) {
			int id = g[i].id, w = g[i].v, v = g[i].v * g[i].p;
			if(p[id][0].size() == 2) { //如果这个物品有2个附件 
				int w1 = p[id][0][0], w2 = p[id][0][1], v1 = p[id][0][0] * p[id][1][0], v2 = p[id][0][1] * p[id][1][1];
				dp[j] = max(dp[j], dp[j-w]+v); //不选, 选择该物品的主件 
				if(j-w-w1-w2 >= 0) dp[j] = max(dp[j], dp[j-w-w1-w2]+v+v1+v2); //不选, 选择该物品的主件和两个附件 
				if(j-w-w1 >= 0) dp[j] = max(dp[j], dp[j-w-w1]+v+v1); //不选, 选择该物品的主件和附件1
				if(j-w-w2 >= 0) dp[j] = max(dp[j], dp[j-w-w2]+v+v2); //不选, 选择该物品的主件和附件2
			}
			else  if(p[id][0].size() == 1) { //如果这个物品有1个附件 
				int w1 = p[id][0][0], v1 = p[id][0][0] * p[id][1][0];
				dp[j] = max(dp[j], dp[j-w]+v); //不选, 选择该物品的主件 
				if(j-w-w1 >= 0) dp[j] = max(dp[j], dp[j-w-w1]+v+v1); //不选, 选择该物品的主件和附件 
			}
			else { //如果一个附件都没有 
				dp[j] = max(dp[j], dp[j-w]+v); //不选, 选择该物品 
			}
		}
	}
	cout << dp[n] << endl;
	return 0;
}