01背包实验指导

《01背包实验指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、0/1背包问题问题描述：给定一个载重量为m,n个物品，其重量为Wi，价值为W，l<=i<=n,要求:把物品装入背包，并使包内物晶价值最大。问题分析：在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。1、递归#includeniostreamn#defineCAPACITY9#defineGOODSNUM5usingnamespacestd;intnVol[GOODSNUM];〃2,3,4,5,4intnValue[GOODSNUM];〃3,7,5,9,8intknapsack(intitemindex,intvol)

2、;intknapsack(intitemindex,intvol){if(itemlndex==0llvol==0)return0;elseif(vol>=nVol[itemindex-1]&&knapsack(itemlndex・1,vol)

3、ack(itemlndex-l,vol);}voidmain(){inti=0,j=0;while(i

4、n(){inti=l,j；intv[GOODSNUM]={3,7,5,9,8};intc[GOODSNUM]={2,3,4,5,4};intfun[GOODSNUM4-1][CAPACITY+1];for(i=1;i<=GOODSNUM;i++){fun[i][0]=0;}for(i=l;iv二CAPACITY;i++){fun[0][i]=0;for(i=l;i<=GOODSNUM;i++)for(j=l；j<=CAPACITY;j++)if(jvc[i・l]){fun[i][j]=fun[i-l][j];}elseif(fun[i-1

5、][j]

6、ODSNUM]={3,7,5,9,8};intselectTable[GOODSNUM][CAPACITY+1]={0};intnKnapsack[CAPACITY4-1]={0};//mostimportantforthefirstcomputionbelowintitemindex,capindex;for(itemIndex=0;itemIndex=nVolume[itemIndex];capIndex—)//注意此处与二维数

7、组的区别if(nKnapsack[capIndex]

8、k[CAPACITY

9、«endl;cout«nTheselecteditemsare:n;for(itemlndex=GOODSNUM-1,capindex=CAPACITY;itemInde