YoungNeal @ 2018-01-11 13:23:48
思路就是转化为01背包,对于每个附件,处理时 它的价值+=主件的价值,重量+=主件的重量 然后在数组末尾再加上两个附件都取的情况 不知道哪里错了
代码风格还算正常,变量名都有意义,应该能理解=.=
谢谢大神帮忙看看啦~
#include<bits/stdc++.h>
using namespace std;
int a[65][5];
int n,m,f[32500];
struct data{
int val,weight,nxt;
}thing[65];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
thing[i].val=x*y;
thing[i].weight=x;
thing[i].nxt=z;
}
for(int i=1;i<=m;i++){
if(thing[i].nxt){
int u=thing[i].nxt;
a[u][1]+=thing[i].val;
a[u][2]+=thing[i].weight;
thing[i].val+=thing[u].val;
thing[i].weight+=thing[u].weight;
}
}
int cnt=m;
for(int i=1;i<=m;i++){
if(a[i][1]){
a[i][1]+=thing[i].val;
a[i][2]+=thing[i].weight;
thing[++cnt].val=a[i][1];
thing[cnt].weight=a[i][2];
}
}
for(int i=1;i<=cnt;i++){
for(int j=n;j>=thing[i].weight;j--)
f[j]=max(f[j],f[j-thing[i].weight]+thing[i].val);
}
printf("%d",f[n]);
return 0;
}
by Salamander @ 2018-01-11 16:44:04
这样做背包可能会同时选主件和主件+附件,这样主件被算了多次
by _WA自动机 @ 2018-01-11 17:08:34
楼上说的对。不能让主件和附件同时被选择。
by YoungNeal @ 2018-01-11 17:27:08
嗯嗯谢谢~
@Salamander
@_WA自动机