挺好懂的, 因为有主件附件, 就把附件的加到主建就行了, 看作是一个。然后用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; }
0.0分
1 人评分