求大神!!!为什么不对QAQ好迷

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

lokiii @ 2017-04-09 11:46:29

我想的是把 只取主,取主和附1,取主和附2,取主和附1附2各作为一个商品存在b里,b【】。a为价值乘价格,b【】。b为价格,这一步核对过了没有错

但是我01背包出来的结果价格总和大于额定价格是为什么QAQ

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct base
{
    int v,p,q,f1,f2;
}a[61];
struct wu
{
    int a,b; //v*p v
}b[200];
int main()
{
    int n,m,j=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
        if(a[i].q>=0)
        {
            if(a[a[i].q].f1==0)
            a[a[i].q].f1=i;
            else
            a[a[i].q].f2=i;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(a[i].q==0)
        {
            if(a[i].f1==0)
            {
                b[j].a=a[i].v*a[i].p/10;
                b[j].b=a[i].v/10;
                j++;
            }
            else if(a[i].f2==0)
            {
                b[j].a=a[i].v*a[i].p/10;
                b[j].b=a[i].v/10;
                j++;
                b[j].a=(a[i].v*a[i].p+a[a[i].f1].v*a[a[i].f1].p)/10;
                b[j].b=(a[i].v+a[a[i].f1].v)/10;
                j++;
            }
            else
            {
                b[j].a=a[i].v*a[i].p/10;
                b[j].b=a[i].v/10;
                j++;
                b[j].a=(a[i].v*a[i].p+a[a[i].f1].v*a[a[i].f1].p)/10;
                b[j].b=(a[i].v+a[a[i].f1].v)/10;
                j++;
                b[j].a=(a[i].v*a[i].p+a[a[i].f2].v*a[a[i].f2].p)/10;
                b[j].b=(a[i].v+a[a[i].f2].v)/10;
                j++;
                b[j].a=(a[i].v*a[i].p+a[a[i].f1].v*a[a[i].f1].p+a[a[i].f2].v*a[a[i].f2].p)/10;
                b[j].b=(a[i].v+a[a[i].f1].v+a[a[i].f2].v)/10;
                j++;
            }
        }
    }
    for(int i=1;i<j;i++)
    printf("%d %d\n",b[i].a,b[i].b);
    int con=j-1,d[61][3200]={0};
    n=n/10;
    for(int i=1;i<=con;i++)  
    for(int j=b[i].b;j<=n;j++)//在这里,背包放入物品后,容量不断的减少,直到再也放不进了  
    {
        d[i][j]=(i==1?0:d[i-1][j]);
        if(j>=b[i].b)
        {
            d[i][j]=max(d[i][j],d[i-1][j-b[i].b]+b[i].a);//no,put
        }
        //if(d[i][j]==d[i-1][j-b[i].b]+b[i].a)
        //printf("%d %d ",d[i][j],i);  
    }
    printf("%d",d[con][n]*10);
    return 0;
}

by BFSBFSBFSBFS @ 2017-04-30 15:59:08

@木落汐loki 因为背包可能取完主+附1又取了主+附2......


by lokiii @ 2017-04-30 21:02:58

Σ(っ °Д °;)っ说的有道理!是我死心眼了。。。谢谢大神!@ BFSBFSBFSBFS


|