算法設計與分析課程設計報告-背包問題的設計與實現(xiàn)(編輯修改稿)
2025-02-14 22:58 本頁面
【文章內(nèi)容簡介】 物品，其重量分別是{2，2，6，5，4}，價值分別是{6，3，5，4，6}，背包的容量為10。根據(jù)動態(tài)規(guī)劃函數(shù)，用一個(n+1)(C+1)的二維表V，V[i][j]表示把前i個物品裝入容量為j的背包中獲得的最大價值。按下述方法來劃分階段：第一階段，只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)V(n1,C)，表明第n個物品被裝入背包，前n1個物品被裝入容量為Cwn的背包中；否則，第n個物品沒有被裝入背包，前n1個物品被裝入容量為C的背包中。依此類推，直到確定第1個物品是否被裝入背包中為止。算法設計設n個物品的重量存儲在數(shù)組w[n]中，價值存儲在數(shù)組v[n]中，背包容量為C，數(shù)組V[n+1][C+1]存放迭代結果，其中V[i][j]表示前i個物品裝入容量為j的背包中獲得的最大價值，數(shù)組x[n]存儲裝入背包的物品，動態(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++) //計算第i行，進行第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)評公示相關推薦
鄂ICP備17016276號-1