原题链接：P1064 [NOIP2006 提高组] 金明的预算方案

感谢帮忙debug的大佬，代码30分，前三点AC，后面WA，分组背包

#include <iostream>
using namespace std;
const long long N = 100, M = 3.2e4 + 10;
long long v[N][5], w[N][5];//只选主件、选主件+附件1、选主件+附件2、选主件+附件1+附件2、不选五种情况花费money和可取得的价值
long long dp[M];
long long cnt;
int main() {
	long long money, n;
	cin >> money >> n;
	for (long long i = 1; i <= n; i++) {//分组的处理
		long long m, pi, zhu;
		cin >> m >> pi >> zhu;
		if (zhu == 0) {
			v[++cnt][0] = m;
			w[cnt][0] = m * pi;
		} else {
			if (v[zhu][1] == 0) {
				v[zhu][1] = m + v[zhu][0];
				w[zhu][1] = m * pi + w[zhu][0];
			} else {
				v[zhu][2] = m + v[zhu][0];
				w[zhu][2] = m * pi + w[zhu][0];
				v[zhu][3] = m + v[zhu][1];
				w[zhu][3] = m * pi + w[zhu][1];
			}

		}
	}

	for (long long i = 1; i <= cnt; i++) {
		for (long long k = money; k >= 1; k--) {
			for (long long j = 0; j <= 4; j++) {
				if (v[i][j] <= k)
					dp[k] = max(dp[k], dp[k - v[i][j]] + w[i][j]);
			}
		}
	}

	cout << dp[money];
	return 0;
}

参考数据 #4

样例输入

4500 12
100 3 0
400 5 0
300 5 0
1400 2 0
500 2 0
800 2 4
1400 5 4
300 5 0
1400 3 8
500 2 0
1800 4 0
440 5 10

样例输出

16700

该程序输出

16100