搜索
9动态规划(背包问题)9.2.4背包问题有n件物品，每件物品有一个重量和一个价值，同时有一个背包容量为wk，要求从n件物品中任取若干件，使重量之和=wk，而价值之和最大。五种不同类型背包1)0—1背包，n件物品，每件物品要么不取，或者全取2)可拆背包，每件物品可以拆开，任意选取3)无限背包，每件物品有无穷多个4)多重背包，每件物品有许多个，但是不是无穷。5)关联背包，有些物品不能独立，必须和别的物品一道选取9.2.4.10—1背包用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}例如n=6,wk=30重量w513710814价值C162818201731数组w[i]第i件物品的重量数组c[i]第i件物品的价值数组g[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。递推关系参考代码：#includeiostream#includecstdio#includealgorithmusingnamespacestd;#defineMAXN1010intc[MAXN],w[MAXN],g[MAXN][MAXN];intmain(){intn,wk,i,j;cinnwk;0123456789101112131415161718192021222324252627282930000000000000000000000000000000001000001616161616161616161616161616161616161616161616161616200000161616161616161628282828284444444444444444444444444430000016161818181818343434343434444446464646466262626262624000001616181818202034343436363844444646545454626262646466500000161618181820203434343636384444515154545462626264647160000016161818182020343434363638444751515454546265656567710(i=0,0=j=wk)g[i][j]=g[i-1][j](i0,jw(i))max(g[i-1][j],g[i-1][j-w[i]]+c[i])(w(i)=j=wk)for(i=1;i=n;i++)cinw[i]c[i];for(j=0;j=wk;j++)g[0][j]=0;for(i=1;i=n;i++)for(j=0;j=wk;j++){if(w[i]j)g[i][j]=g[i-1][j];elseg[i][j]=max(g[i-1][j],g[i-1][j-w[i]]+c[i]);}coutg[n][wk];return0;}优化一：观察G[i][j]可以发现，第i行只与i-1行进行比较，可以节约空间，防止数据量过大，不使用二维数组。#includeiostream#includecstdio#includealgorithmusingnamespacestd;#defineMAXN1010intc[MAXN],w[MAXN],g[1][MAXN];intmain(){intn,wk,i,j;cinnwk;for(i=1;i=n;i++)cinw[i]c[i];for(j=0;j=wk;j++)g[0][j]=0;for(i=1;i=n;i++){for(j=w[i];j=wk;j++)g[1][j]=max(g[0][j],g[0][j-w[i]]+c[i]);for(j=0;j=wk;j++)g[0][j]=g[1][j];}coutg[1][wk];return0;}优化二：同样可以使用一维数组实现。参考代码：#includeiostream#includecstdio#includealgorithmusingnamespacestd;#defineMAXN1010intc[MAXN],w[MAXN],g[MAXN];intmain(){intn,wk,i,j;cinnwk;for(i=1;i=n;i++)cinw[i]c[i];for(i=1;i=n;i++)for(j=wk;j=w[i];j--)//此处循环不能写成升序g[j]=max(g[j],g[j-w[i]]+c[i]);coutg[wk]endl;return0;}j按照wk…w[i]逆循环，是因为要保证第i次循环中的状态g[i][j]是由状态g[i-1][j-w[i]]递推而来。换句话说，正是为了保证每件物品只选一次，保证在选入第i件物品依据的是未选入该件物品的子结果g[i-1][j-w[i]]。顺推结果：01234567891011121314151617181920212223242526272829000000000000000000000000000000010000016161616163232323232484848484864646464648080808080逆推结果：01背包+路径记录+（价值最大/恰好装满）#includeiostream#includestring#includealgorithmusingnamespacestd;#defineMAXN1010#defineINF0x3F3F3F3F//作为无穷大的数，保证无穷大+无穷大=无穷大intc[MAXN],w[MAXN],g[MAXN],numb[MAXN][MAXN];intmain(){intn,wk,i,j;cinnwk;//memset(g,-INF,sizeof(g));g[0]=0;//要求恰好装满背包memset(g,0,sizeof(g));//只希望价值尽量大for(i=1;i=n;i++)cinw[i]c[i];for(i=1;i=n;i++)for(j=wk;j=w[i];j--)//此处循环不能写成升序if(g[j]g[j-w[i]]+c[i]){g[j]=g[j-w[i]]+c[i];for(intp=1;p=n;p++)numb[j][p]=numb[j-w[i]][p];numb[j][i]+=1;}coutg[wk]endl;for(i=1;i=n;i++)if(numb[wk][i])coutw[i];coutendl;//for(i=0;i=wk;i++){//打表numb、重量、价值//for(j=1;j=n;j++)//coutnumb[i][j];//coutig[i]endl;//}return0;}9.2.4.2可拆背包每件物品可以拆开，任意选取n=6,wk=30重量w5137108140123456789101112131415161718192021222324252627282930000000000000000000000000000000001000001616161616161616161616161616161616161616161616161616价值C162818201731基本思想：（贪心算法）按照c(i)/w(i)的值由大到小排序1618312817205714138103.22.572.212.152.122答案:16+18+31+28*2/139.2.3.3无限背包(完全背包)，每件物品有无穷多个如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0=k*w[i]=v}例如n=6,wk=29重量w513710814价值C162818201731012345678910111213141516171819202122232425262728290000000000000000000000000000000100000161616161632323232324848484848646464646480808080802000001616161616323232323248484848486464646464808080808030000016161818183232343436484850505264646666688080828284400000161618181832323434364848505052646466666880808282845000001616181818323234343648485050526464666668808082828460000016161818183232343436484850505264646666688080828284参考代码一：#includeiostream#includecstdio#includealgorithmusingnamespacestd;#defineMAXN1010intc[MAXN],w[MAXN],g[1][MAXN];intmain(){intn,wk,i,j;cinnwk;for(i=1;i=n;i++)cinw[i]c[i];for(j=0;j=wk;j++)g[0][j]=0;for(i=1;i=n;i++){for(j=w[i];j=wk;j++)g[1][j]=max(g[0][j],g[1][j-w[i]]+c[i]);for(j=0;j=wk;j++)g[0][j]=g[1][j];}coutg[1][wk];return0;}参考代码二：0(i=0,0=j=wk)g[i][j]=g[i-1][j](i0,jw(i))max(g[i-1][j],g[i][j-w[i]]+c[i])(w(i)=j=wk)#includeiostream#includestring#includealgorithmusingnamespacestd;#defineMAXN1010#defineINF0x3F3F3F3F//作为无穷大的数，保证无穷大+无穷大=无穷大intc[MAXN],w[MAXN],g[MAXN],numb[MAXN][MAXN];intmain(){intn,wk,i,j;cinnwk;//memset(g,-INF,sizeof(g));g[0]=0;//要求恰好装满背包memset(g,0,sizeof(g));//只希望价值尽量大for(i=1;i=n;i++)cinw[i]c[i];for(i=1;i=n;i++)for(j=w[i];j=wk;j++)//此处循环不能写成反序if(g[j]g[j-w[i]]+c[i]){g[j]=g[j-w[i]]+c[i];for(intp=1;p=n;p++)numb[j][p]=numb[j-w[i]][p];numb[j][i]+=1;}coutg[wk]endl;for(i=1;i=n;i++)if(numb[wk][i])coutw[i]numb[wk][i]endl;//for(i=0;i=wk;i++){//打表numb、重量、价值//for(j=1;j=n;j++)//coutnumb[i][j];//coutig[i]endl;//}return0;}9.2.4.4多重背包：每件物品有许多个