01背包变形问题

挺好懂的， 因为有主件附件， 就把附件的加到主建就行了， 看作是一个。然后用01背包问题解法。

#include <bits/stdc++.h>
using namespace std;
const int N = 101010;

int n, m, sum = 1, sum2 = 1;
int a[N], a1[N];
int w, v, f[N], p;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> w >> v >> p;
		int qq = 0;
		qq = w * v;//乘上价值
		if (!p) {
			a1[sum2++] = w;
			a[sum++] = qq;
		} 
		else{
			a[p] += qq;
			a1[p] += w;
		}
	}
	sum -= 1;
	for (int i = 1; i <= sum; i++){
		for (int j = n; j >= a1[i]; j--){
			f[j] = max(f[j], f[j - a1[i]] + a[i]) ;
		}
	}
	cout << f[n] <<endl;
	return 0;
}