AcWing 487. 金明的预算方案
原题链接
中等
作者:
fancywing
,
2021-01-19 20:04:01
,
所有人可见
,
阅读 299
转化成分组背包
#include <iostream>
#include <vector>
#include <algorithm>
#define v first
#define w second
using namespace std;
typedef pair<int, int> PII;
// N:物品数量,M:背包总量
const int N = 65, M = 32010;
int n, m;
PII master[N];
vector<PII> servent[N];
int f[M];
int main(){
cin >> m >> n;
for(int i = 1; i<= n; i++){
int v,w,q;
cin >> v >> w >> q;
if(!q) master[i] = {v, v*w};
else servent[q].push_back({v, v*w});
}
for(int i = 1; i<= n; i++){
for(int j = m; j >= 0; j--){
for(int k = 0; k < 1 << servent[i].size();k++){ // k来枚举所有组合的方案
// 根据题意,每种方案主件都是必选
int v = master[i].v;
int w = master[i].w;
for(int u = 0; u < servent[i].size(); u++){ // u来枚举附件
if(k >> u & 1){ // 当前组合方案是否包含附件u
v += servent[i][u].v;
w += servent[i][u].w;
}
}
if(j >= v) f[j] = max(f[j], f[j-v]+w);
}
}
}
cout<< f[m]<<endl;
return 0;
}