题目描述
AcWing 487. 金明的预算方案
样例
算法《多重背包的感觉来做的》
(暴力枚举) $O(n*m*4)$
时间复杂度
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int N = 70,M = 32010;
int n,m;
int f[M];
int w[N],v[N],id[N];
vector <int> p[N];
int main () {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> id[i];
w[i] *= v[i];
if (id[i]) p[id[i]].push_back (i);
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 1; j++ ) p[i].push_back(0);
for (int i = 1; i <= n; i++) {
if (id[i]) continue;
for (int j = m; j >= 0; j--) {
int a,b;
a = v[i],b = w[i];
if (j >= a) f[j] = max (f[j], f[j - a] + b);
a = v[i] + v[p[i][0]], b = w[i] + w[p[i][0]];
if (j >= a) f[j] = max (f[j],f[j - a] + b);
a = v[i] + v[p[i][1]], b = w[i] + w[p[i][1]];
if (j >= a) f[j] = max (f[j],f[j - a] + b);
a = v[i] + v[p[i][1]] + v[p[i][0]], b = w[i] + w[p[i][1]] + w[p[i][0]] ;
if (j >= a) f[j] = max (f[j],f[j - a] + b);
}
}
cout << f[m] << endl;
return 0;
}