XXXX

　大 學 計 算 機 學 院 實 驗 報 告

　 計算機學院

　2017

　級

　軟件工程

　專業

　5

　班

　指導教師

　學號

　姓名

　2019

　年 10

　月 21

　日

　成績

　 課程名稱 算法分析與設計 實驗名稱 動態規劃 ---0-1 背包問題①理解遞歸算法的概念

　實驗目的

?、谕ㄟ^模仿 0-1 背包問題，了解算法的思想③練習 0-1 背包問題算法

　實驗儀器 電腦、 jdk 、 eclipse 和器材

　 實驗：

　0-1 背包算法：給定

　N 種物品，每種物品都有對應的重量

　weight 和價值 value ，一個容

　量為 maxWeight 的背包，問：應該如何選擇裝入背包的物品，使得裝入背包的物品的總價值

　最大。（面對每個物品，我們只有拿或者不拿兩種選擇，不能選擇裝入物品的某一部分，也 實

　驗 不能把同一個物品裝入多次）代碼如下所示：

　內 public class

　KnapsackProblem {

　容 /**

　 、

　上 * @paramweight 物品重量

　機 * @paramvalue 物品價值 調 * @parammaxweight

　背包最大重量

　試

　程 *

　@return maxvalue[i][j] 中， i 表示的是前 i 個物品數量，

　j 表示的是重量

　序 */

　 、 public

　 static

　 int knapsack(

　int

　[]

　 weight , int

　[]

　 value , int

　 maxweight ){

　 程

　序

　運

　行

　結

　果

　實

　驗

　內 int

　 n = ;

　包問題的算法思想：將前 i 個物品放入容量 容 為 w 的背包中的最大價值。有如下兩種情況：

　、 ①若當前物品的重量小于當前可放入的重量，便可考慮是 上 否要將本件物品放入背包中或者將背包中的某些物品拿出 機 來再將當前物品放進去；放進去前需要比較（不放這個物 調 品的價值）和（這個物品的價值放進去加上當前能放的總 試 重量減去當前物品重量時取

　 i-1 個物品是的對應重量時候 程 的最高價值），如果超過之前的價值，可以直接放進去，反 序 之不放。

　 、

　 ②若當前物品的重量大于當前可放入的重量，則不放入 程 背包問題利用動態規劃的思路可以這樣理解：階段是“物 序 品的件數”，狀態就是“背包剩下的容量” ，f[i,v]

　 表示設 運 從前 i 件物品中選擇放入容量為 V 的背包的最大價值。那 行 么狀態轉移的方法為

　:

　 結

　 f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}

　果

　這個方程可以理解為：只考慮子問題“將前 i 個物品放入

　 容量為 v

　的背包中的最大價值” 那么可以考慮不放入

　i

　，最

　大價值就和 i

　無關，就是 f[i-1][v], 如果放入第

　i

　個物品，

　價值就是 f[i-1][v-w[i]]+value[i], 只取最大值即可。

　實

　驗

　內

　容

　、

　上

　機

　調

　試

　程

　序

　、

　程

　序

　運

　行

　結

　果

推薦訪問： 背包 規劃 實驗