此类背包典型的关系是若想选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("%dn",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("%dn",dp[tot]); } return 0;} (编辑:安卓应用网)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|