题意:有钱sum,给出n组选择,每种选择有m个物品w,要买物品先必须买盒子,物品价格为w[i],价值p[i]。
然后给出每种选择的一些物品的价格还有价值求取得最大值。
物品依赖于盒子。
按照背包九讲的做法:
先对每组选择里的所有物品进行0-1背包处理,但背包容量为(总容量-盒子容量);
然后跟上一组的状态比较来决定这一组选择 是选还是不选,取其中的较大值。
用dp[i][j]表示第i组背包容量为j时的最大价值。
在转移状态之前当前组选择的初始化:
for(j=0;j<q;j++)//q表示盒子的价格 dp[i][j]=-INF;//当钱<盒子价格时,无价值,注意不要赋值为0, 这题有 重量为0,但有价值的物品。
//例如 这组数据
1 10 11 1 0 11
盒子都买不起,所以输出0
但以上如果赋值为0,程序会输出11,是错误的。 for(j=q;j<=sum;j++) dp[i][j]=dp[i-1][j-q];//当钱>=盒子价格时,让前一组状态先买个盒子,买好盒子之后状态变为dp[i-1][j-q];
二维数组版:
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 1<<29 int n,sum,m,q; int w[11],p[11]; int dp[51][100003]; int main() { int i,j,x; while(~scanf("%d%d",&n,&sum)) { memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d%d",&q,&m); for(x=1;x<=m;x++) scanf("%d%d",&w[x],&p[x]); //注意初始化,上面已做出解释 for(j=0;j<=q;j++) dp[i][j]=-INF; for(j=q;j<=sum;j++) dp[i][j]=dp[i-1][j-q]; //按照背包九讲的做法,将当前组的物品进行0-1背包处理。 for(x=1;x<=m;x++) for(j=sum;j>=w[x];j--) dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+p[x]); //跟上一组的状态进行比较,选择较大的值, //如果选dp[i][j]说明选了当前组的物品和盒子, //如果选dp[i-1][j]说明没有选当前组的物品和盒子。 for(j=0;j<=sum;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]); } printf("%d\n",dp[n][sum]); } return 0; }
滚动数组版:
View Code
原文链接:https://www.f2er.com/javaschema/286057.html#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 1<<29 int n,q; int w,p; int dp[100003],tmp[100003]; int main() { int i,&m); for(j=0;j<q;j++) tmp[j]=-INF; for(j=q;j<=sum;j++) tmp[j]=dp[j-q]; for(x=1;x<=m;x++) { scanf("%d%d",&w,&p);//写在循环内,边读入边对其进行0-1背包,省去了2个数组 for(j=sum;j>=w;j--) tmp[j]=max(tmp[j],tmp[j-w]+p); } for(j=0;j<=sum;j++) dp[j]=max(dp[j],tmp[j]); } printf("%d\n",dp[sum]); } return 0; }