这种思路哪里有问题呢?

P1064 [NOIP2006 提高组] 金明的预算方案

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自动机


|