HDU 3449 有依赖的01背包

给出n个盒子，和总钱数w

对于n个盒子，首先买盒子需要花费m，然后可以买盒子中的物品，每个物品分别有其花费a[i].w和价值a[i].v

典型的有依赖的01背包

mark存储前i-1个盒子的dp值

然后对于当前盒子，先不考虑其盒子的花费进行01背包

然后对于mark数组的得到的每个新值mark[i}，去更新dp[i+a[i].m];

#include "stdio.h"
#include "string.h"

struct node
{
    int n,m;
    int w[11],v[11];
} a[51];

int dp[100010],mark[100010];

int Max(int a,int b)
{
    if (a<b) return b;
    else return a;
}
int main()
{
    int n,w,i,j,k,ans;
    while (scanf("%d%d",&n,&w)!=EOF)
    {
        for (i=1; i<=n; i++)
        {
            scanf("%d%d",&a[i].m,&a[i].n);
            for (j=1; j<=a[i].n; j++)
                scanf("%d%d",&a[i].w[j],&a[i].v[j]);
        }

        memset(dp,sizeof(dp));

        for (i=1; i<=n; i++)
        {
            for (k=0; k<=w; k++)
                mark[k]=dp[k];
            for (j=1; j<=a[i].n; j++)
                for (k=w; k>=a[i].w[j]; k--)
                {
                    if (mark[k-a[i].w[j]] + a[i].v[j] >mark[k])
                        mark[k]=mark[k-a[i].w[j]]+a[i].v[j];
                }
            for (k=0; k+a[i].m<=w; k++)
                dp[k+a[i].m]=Max(dp[k+a[i].m],mark[k]);
        }
        ans=0;
        for (i=0; i<=w; i++)
            ans=Max(ans,dp[i]);
        printf("%dn",ans);


    }
    return 0;
}

（编辑：李大同）

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