此类背包典型的关系是若想选b，你必须先选a，从而产生了一层依赖关系，然后给你一定限量的总钱数，让你买最大价值的东西
就让我们从hdu 3449 来搞定这类最简单的依赖背包吧
有很多个箱子，想买箱子中的物品必须先买下箱子，典型的依赖背包
dp[i][j]代表前i个箱子花费j的钱能获得的最大价值，则可以想到每次在对一个箱子进行dp更新状态时都应该利用前面的结果来更新
以前做那道金明的预算方案时，就是没有利用上层的结果来更新才一直错，dp的本质都被我给忽略了，囧！
View Code
- #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,0,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("%d\n",dp[n][tot]);
}
return 0;
}
也可以不用tmp数组
View Code
- #include<cstdio>
#include<cstring>
int dp[60][100010];
int max(int a,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d%d",&m);
for(j=0;j<p;j++) dp[i][j]=-1;
for(j=p;j<=tot;j++) dp[i][j]=dp[i-1][j-p];//继承上一层的结果,j-p是因为一定要买箱子
for(j=1;j<=m;j++)
{
scanf("%d%d",&v);
for(k=tot;k>=w;k--)
{
if(dp[i][k-w]!=-1)
dp[i][k]=max(dp[i][k],dp[i][k-w]+v);//01背包部分
}
}
for(j=tot;j>=0;j--)//如果能更新上一层的状态，就更新。
dp[i][j]=max(dp[i][j],dp[n][tot]);
}
return 0;
}
还可以用一维的
dp[i]代表花i的钱能得到的最大价值
View Code
- #include<stdio.h>
#include<string.h>
int dp[100010];
int tmp[100010];
int max(int a,p,v,&tot)!=EOF)
{
memset(dp,sizeof(dp));
for(i=0;i<n;i++)
{
scanf("%d%d",&m);
memcpy(tmp,dp,sizeof(dp));//继承前面的
for(j=0;j<m;j++)
{
scanf("%d%d",&v);
for(k=tot-p;k>=w;k--)//按照背包九讲的说法，先将附件进行1次01背包
tmp[k]=max(tmp[k],tmp[k-w]+v);
}
for(j=p;j<=tot;j++)//更新能更新的
dp[j]=max(dp[j],tmp[j-p]);
}
printf("%d\n",dp[tot]);
}
return 0;}
