hdu3449 有依赖的背包问题

不解释了，我估计难讲清楚，看代码吧。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

int f[100005],d[100005];
int main()
{
    int n,ww;
    while(scanf("%d%d",&n,&ww)!=EOF){
        int i,j,k,v[101],mi[101],c[101][25],w[101][25];
        memset(f,0,sizeof(f));
        memset(d,0,sizeof(d));
        for(i=1;i<=n;i++){
            scanf("%d%d",&v[i],&mi[i]);
            for(j=1;j<=mi[i];j++){
                scanf("%d%d",&c[i][j],&w[i][j]);
            }
        }
        for(i=1;i<=n;i++){
            for(k=0;k<=ww-v[i];k++) f[k+v[i]]=d[k];
            for(k=1;k<=mi[i];k++)
                for(j=ww;j>=v[i]+c[i][k];j--){
                    f[j]=max(f[j],f[j-c[i][k]]+w[i][k]);
                }
            for(k=v[i];k<=ww;k++) d[k]=max(f[k],d[k]);
        }
        printf("%d\n",d[ww]);
    }
}

hdu3449 有依赖的背包问题,布布扣,bubuko.com

hdu3449 有依赖的背包问题

原文：http://blog.csdn.net/cnh294141800/article/details/22984539