實(shí)驗(yàn)報(bào)告：動(dòng)態(tài)規(guī)劃

1、XXXX大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告計(jì)算機(jī)學(xué)院2017 級(jí)軟件工程專(zhuān)業(yè)班指導(dǎo)教師學(xué)號(hào) 姓名2019年10月21日 成績(jī)課程名稱算法分析與設(shè)計(jì)實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃一-0-1背包問(wèn)題實(shí)驗(yàn)?zāi)康睦斫膺f歸算法的概念通過(guò)模仿0-1背包問(wèn)題，了解算法的思想練習(xí)0-1背包問(wèn)題算法實(shí)驗(yàn)儀器 和器材電腦、jdk、eclipse實(shí) 驗(yàn) 內(nèi) 容、 上 機(jī) 調(diào) 試 程序、 程 序 運(yùn) 彳亍 結(jié)果實(shí)驗(yàn)：0-1背包算法：給定N種物品，每種物品都有對(duì)應(yīng)的重量weight和價(jià)值value,-個(gè)容 量為maxWeight的背包，問(wèn)：應(yīng)該如何選擇裝入背包的物品，使得裝入背包的物品的總價(jià)值 最大。(面對(duì)每個(gè)物品，我們只有拿或者不拿兩種選擇，不

2、能選擇裝入物品的某一部分，也 不能把同一個(gè)物品裝入多次)代碼如下所示：public class KnapsackProblem /*param weight 物品重量param value 物品價(jià)值param maxweight背包最大重量* return maxvalueij中，i表示的是前i個(gè)物品數(shù)量，j表示的是重量*/public static int knapsack(int weight, int value, int maxweight)l-wl me nu_5 e-a rclhjp42 43 4447 48g5254 15 51- pQ59 巨仞61 !62 65 &4JrIJ

3、I Kh-b p s-a ck Prolb- le m Ja va 陽(yáng);昆盡V苯南遂*赫克的俏值)和:摩個(gè)物品的仿值放進(jìn)去 KnapsackPrab-le-m Java Applicatan C:Pfdgram File-sJavajre-1 .S.D_1 51 者桓王里為s是時(shí)，背包的取大的伯廿直是:： 11mt n 一包問(wèn)題的算法思想：將前i個(gè)物品放入容量 int n ,為w的背包中的最大價(jià)值。有如下兩種情況： 若當(dāng)前物品的重量小于當(dāng)前可放入的重量，便可考慮是 否要將本件物品放入背包中或者將背包中的某些物品拿出 來(lái)再將當(dāng)前物品放進(jìn)去；放進(jìn)去前需要比較（不放這個(gè)物 品的價(jià)值）和（這個(gè)物品的價(jià)值放進(jìn)去加上當(dāng)前能放的總 重量減去當(dāng)前物品重量時(shí)取i-1個(gè)物品是的對(duì)應(yīng)重量時(shí)候 的最高價(jià)值），如果超過(guò)之前的價(jià)值，可以直接放進(jìn)去，反 之不放。若當(dāng)前物品的重量大于當(dāng)前可放入的重量，則不放入 背包問(wèn)題利用動(dòng)態(tài)規(guī)劃的思路可以這樣理解：階段是“物 品的件數(shù)”，狀態(tài)就是“背包剩下的容量”，fi,v表示設(shè) 從前i件物品中選擇放入容量為V的背包的最大價(jià)值。那 么狀態(tài)轉(zhuǎn)移的方法為:fiv=maxfi-1v,fi-1v-wi+ci這個(gè)方程可以理解為：只考慮子問(wèn)題“將前i個(gè)物品放入容量為v的背包中的最大價(jià)值”那么可以考慮不放入i，最 大價(jià)值就和i無(wú)關(guān)，就是fi-1v,如果放入第