题解 | #[NOIP2006]金明的预算方案#

我来提供一下我自己想出来的思路
我这个思路的优点是，当附件有很多很多个的时候，你不用去把每种情况都穷举出来
首先，我定义了两个二维数组，二维数组itemv和二维数组itemw，itemv和itemw当中的每一个数组的第一个元素是主件，其余的为附件
然后我的dp也是二维数组，第一个i代表前i个物体，第二个j代表的是价格的下标
然后关键来了，我强行把第一个主件给它加上去，然后剩余附件使用选择性的加上去，然后这样主件和他的附件过完一轮之后，与上一个主件附件进行比较大小，如果这次主件附件加上去比它大，那就保留，否则就回到上一次的进度。

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> itemv;//这个二维数组中的每一个数组的第一个元素是主件的价格，其余的为附件的价格
vector<vector<int>> itemw;//这个二维数组中的每一个数组的第一个元素是主件的重要程度，其余的为附件的重要程度
int dp[70][33000];//第一个i代表前i个物体，第二个j代表的是价格的下标
int id[10000];
void solve() {
	vector<int> temp(100, 0);
	itemv.push_back(temp);
	itemw.push_back(temp);
	int n, m;
	cin >> n >> m;
	for (int i = 1;i <= m;i++) {
		int v, p, q;
		cin >> v >> p >> q;
		if (q <= 0) {
			itemv.push_back(vector<int>(1, v));
			itemw.push_back(vector<int>(1, p));
			id[i] = id[i - 1] + 1;
		}
		else {
			itemv[id[q]].push_back(v);
			itemw[id[q]].push_back(p);
			id[i] = id[i - 1];//因为它输入的q是主件的行数，所以需要一个id数组来转换一下
		}
	}
	for (int i = 1;i < itemv.size();i++) {
		for (int j = 0;j < itemv[i].size();j++) {
				if (j == 0) {				//如果是主件
					for (int k = n;k >= itemv[i][0];k--) {
						dp[i][k] = dp[i - 1][k - itemv[i][j]] + itemv[i][j] * itemw[i][j];	//强行把当前这个主件给加上去
					}
				}
				else {					    //如果是附件
					for (int k = n;k >= itemv[i][0] + itemv[i][j];k--) {		//这里itemv[i][0] + itemv[i][j]就是主件和当前所对应的附件的价格相加后的值
						dp[i][k] = max(dp[i][k], dp[i][k - itemv[i][j]] + itemv[i][j] * itemw[i][j]);
					}
				}
		}
		for (int k = 0;k <= n;k++) {		
			dp[i][k] = max(dp[i][k], dp[i - 1][k]);		//在价格为k时，如果加完之后还没有上一轮加得多，那么就返回上一轮的进度
		}
	}
	cout << dp[itemv.size() - 1][n] << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}