算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告-背包問題的設(shè)計(jì)與實(shí)現(xiàn)(編輯修改稿)
2025-02-14 22:58 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 物品，其重量分別是{2，2，6，5，4}，價(jià)值分別是{6，3，5，4，6}，背包的容量為10。根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)(C+1)的二維表V，V[i][j]表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。按下述方法來(lái)劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)V(n1,C)，表明第n個(gè)物品被裝入背包，前n1個(gè)物品被裝入容量為Cwn的背包中；否則，第n個(gè)物品沒有被裝入背包，前n1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。算法設(shè)計(jì)設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組w[n]中，價(jià)值存儲(chǔ)在數(shù)組v[n]中，背包容量為C，數(shù)組V[n+1][C+1]存放迭代結(jié)果，其中V[i][j]表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組x[n]存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解0/1背包問題的算法如下：int KnapSack(int n, int w[ ], int v[ ]) { for (i=0。 i=n。 i++) //初始化第0列 V[i][0]=0。 for (j=0。 j=C。 j++) //初始化第0行 V[0][j]=0。 for (i=1。 i=n。 i++) //計(jì)算第i行，進(jìn)行第i次迭代 for (j=1。 j=C。 j++) if (jw[i]) V[i][j]=V[i1][j]。 else V[i][j]=max(V[i1][j], V[i1][jw[i]]+v[
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1