HDU 3449 依赖背包

http://acm.hdu.edu.cn/showproblem.php?pid=3449

http://www.cnblogs.com/wuyiqi/archive/2011/11/26/2264283.html

#include<cstdio>
#include<cstring>
int dp[60][100010];
int tmp[100010];
int max(int a,int b){return a>b?a:b;}
int main()
{
    int n,tot,i,j,k;
    while(scanf("%d%d",&n,&tot)!=EOF)
    {
        int p,m,w,v;
        memset(dp,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            memset(tmp,-1,sizeof(tmp));
            scanf("%d%d",&p,&m);
            for(j=p;j<=tot;j++)
                tmp[j]=dp[i-1][j-p];//继承上一层的结果
            for(j=1;j<=m;j++)
            {
                scanf("%d%d",&w,&v);
                for(k=tot;k>=w;k--)
                {
                    if(tmp[k-w]!=-1)
                    tmp[k]=max(tmp[k],tmp[k-w]+v);//01背包部分
                }
            }
            for(j=tot;j>=0;j--)//如果能更新上一层的状态，就更新。
                dp[i][j]=max(tmp[j],dp[i-1][j]);
        }
        printf("%dn",dp[n][tot]);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!