9动态规划(02背包问题)

《9动态规划(02背包问题)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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的背包可以获

2、得的最大价值。则其状态转移方程便是：状态转移方程便是：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的背包可以获得的最大价值。012345678910111213141516171819202122232425262728293000000000000000000000000000000000

3、10000016161616161616161616161616161616161616161616161616162000001616161616161616282828282844444444444444444444444444300000161618181818183434343434344444464646464662626262626240000016161818182020343434363638444446465454546262626464665000001616181818202034343

4、4363638444451515454546262626464716000001616181818202034343436363844475151545454626565656771递推关系0(i=0,0<=j<=wk)g[i][j]=g[i-1][j](i>0,j#include#includeusingnamespac

5、estd;#defineMAXN1010intc[MAXN],w[MAXN],g[MAXN][MAXN];intmain(){intn,wk,i,j;cin>>n>>wk;for(i=1;i<=n;i++)cin>>w[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])

6、;}cout<#include#includeusingnamespacestd;#defineMAXN1010intc[MAXN],w[MAXN],g[1][MAXN];intmain(){intn,wk,i,j;cin>>n>>wk;for(i=1;i<=n;i++)cin>>w[i]>

7、>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];}cout<#include#includeusingnamesp

8、acestd;#defineMAXN1010intc[MAXN],w[MAXN],g[MAXN];intmain(){intn,wk,i,j;cin>>n>>wk;for(i=1;i<=n;i++)cin>>w[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]);cout<<