資訊專欄INFORMATION COLUMN
摘要：背包是動(dòng)態(tài)規(guī)劃中比較簡(jiǎn)單的一個(gè)問(wèn)題，其中的關(guān)鍵在于找到狀態(tài)轉(zhuǎn)換方程。表示四個(gè)物品放入大小為的背包中的最大值。就是五種商品放入容量為的背包中的最大價(jià)值，這正好就是題目的答案。
01背包是動(dòng)態(tài)規(guī)劃中比較簡(jiǎn)單的一個(gè)問(wèn)題，其中的關(guān)鍵在于找到狀態(tài)轉(zhuǎn)換方程。
假設(shè)編號(hào)分別為a,b,c,d,e的五件物品，重量分別是2,2,6,5,4，價(jià)值分別是6,3,5,4,6，現(xiàn)在有一個(gè)承重為10的背包，如何裝入物品具有最大價(jià)值？
思路分析首先假設(shè)有一個(gè)國(guó)王且手下有大臣A和大臣B，聰明的國(guó)王將這個(gè)問(wèn)題分為放入物品a和不放入物品a兩種情況。然后國(guó)王告訴大臣A假如已經(jīng)放了物品a, 那么剩下b,c,d,e四件商品放入大小為8的背包中的最大價(jià)值（其中8來(lái)自于總重量10減去物品a的重量2），然后再告訴大臣B假如沒有放入物品a, 那么在b,c,d,e四件商品中放入大小為10的背包中的最大價(jià)值。
而國(guó)王只需要比較兩個(gè)大臣的答案就可以得到最終答案。大臣A采用同樣方法把任務(wù)分給手下有A1和A2兩個(gè)人，大臣B同理。依次下去，即可得到最終的答案。
以上可以看出，關(guān)鍵步驟是將問(wèn)題分解為放入物品a與不放入物品a兩種情況中的最大值，并推廣的所有的物品。這也是01的由來(lái)。
用圖形表示出來(lái)就是下面這張表。
首先注意的是該表是從左下開始填的，左邊紫色列標(biāo)示物品編號(hào)，并對(duì)應(yīng)的有重量與價(jià)值，第一行標(biāo)示背包重量。(b, 5)表示b、c、d、e四個(gè)物品放入大小為5的背包中的最大值。(a, 10)就是abcde五種商品放入容量為10的背包中的最大價(jià)值，這正好就是題目的答案。
現(xiàn)在我們開始學(xué)怎么填這張表，先隨便挑一個(gè)表格(a，9)，此時(shí)背包容量為9，可以選abcde五種物品，我們要找出容量的最大值，根據(jù)上述思路分為放入物品a和不放入物品a兩種情況。
情況a: 假如放入物品a, 則背包容量變?yōu)?-2=7，還剩b,c,d,e四種物品。所以該情況下的最大值 = (b,7) + 物品a的價(jià)值6，即9+6
情況b: 假如不放入物品a, 背包容量不變?yōu)?，還剩b,c,d,e四種物品。所以該情況下的最大值 = (b, 9)，即10
所以現(xiàn)在(a, 9) = max( (b,7)+6, b(9) ) = max(9+6，10) = 15。
同樣的步驟填滿其他的表格即可。
代碼實(shí)現(xiàn)下面是方法2的js實(shí)現(xiàn)
function packageMaxValue(weight, value, size){
// 省略參數(shù)合法性校驗(yàn)
let bagMatrix = []
for(let w = 0; w <= size; w++) {
// js不能直接創(chuàng)建二維數(shù)組，所以在此初始化數(shù)組
bagMatrix[w] = []
for (let j = 0; j < 5; j++) {
// 背包的容量為0，那么一個(gè)東西也裝不下，此時(shí)的值肯定也是為0
if(w === 0) {
bagMatrix[w][j] = 0
continue
}
// 背包的容量小于物品j的重量，那么就沒有上述情況a了
if(w < weight[j]){
bagMatrix[w][j] = bagMatrix[w][j-1] || 0
continue
}
bagMatrix[w][j] = Math.max((bagMatrix[w-weight[j]][j-1] || 0) + value[j], bagMatrix[w][j-1] || 0)
}
}
return bagMatrix
}
let weight = [4, 5, 6, 2, 2]
let value = [6, 4, 5, 3, 6]
console.log(packageMaxValue(weight, value, 10))
參考：
動(dòng)態(tài)規(guī)劃之01背包問(wèn)題（最易理解的講解）
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/86439.html
摘要：狀態(tài)轉(zhuǎn)移方程背包問(wèn)題的狀態(tài)轉(zhuǎn)移方程是其中即表示前件物品恰放入一個(gè)容量為的背包可以獲得的最大價(jià)值。求解將哪些物品裝入背包可使這些物品的體積總和不超過(guò)背包容量，且價(jià)值總和最大。 01背包 01背包的概念 有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。從這個(gè)題目中可以看出，01背包的特點(diǎn)就是：每種物品僅有一件，可以選擇放或...
摘要：背包問(wèn)題題目給定種物品和一個(gè)容量為的背包，物品的體積是，其價(jià)值為。用子問(wèn)題定義狀態(tài)其狀態(tài)轉(zhuǎn)移方程是。 P01: 01背包問(wèn)題 題目 給定 N 種物品和一個(gè)容量為 V 的背包，物品 i 的體積是 wi，其價(jià)值為 ci 。(每種物品只有一個(gè))問(wèn)：如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？ 面對(duì)每個(gè)物品，我們只有選擇放入或者不放入兩種選擇，每種物品只能放入一次。 我們用之前同...
摘要：背包給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。 01背包 給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。 const tList = [1, 2, 3, 4, 5] // 物品體積 const vList = [3, 4, 10, 7, 4] // 物品價(jià)值 const...
摘要：背包問(wèn)題具體例子假設(shè)現(xiàn)有容量的背包，另外有個(gè)物品，分別為，，。最后，就是動(dòng)態(tài)規(guī)劃的思路了。而前個(gè)物體放入容量為的背包，又可以轉(zhuǎn)化成前個(gè)物體放入背包的問(wèn)題。 背包問(wèn)題具體例子：假設(shè)現(xiàn)有容量10kg的背包，另外有3個(gè)物品，分別為a1，a2，a3。物品a1重量為3kg，價(jià)值為4；物品a2重量為4kg，價(jià)值為5；物品a3重量為5kg，價(jià)值為6。將哪些物品放入背包可使得背包中的總價(jià)值最大？ 首先...
摘要：動(dòng)態(tài)規(guī)劃概念動(dòng)態(tài)規(guī)劃過(guò)程每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。相關(guān)文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之四約瑟夫環(huán)王者編程大賽之五最短路徑 首發(fā)于 樊浩柏科學(xué)院 服務(wù)目前每月會(huì)對(duì)搬家?guī)煾颠M(jìn)行評(píng)級(jí)，根據(jù)師傅的評(píng)級(jí)排名結(jié)果，我們將優(yōu)先保證最優(yōu)師傅的全天訂單。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...
閱讀 1037·2023-04-25 15:42
閱讀 3637·2021-11-02 14:38
閱讀 2919·2021-09-30 09:48
閱讀 1469·2021-09-23 11:22
閱讀 3450·2021-09-06 15:02
閱讀 3214·2021-09-04 16:41
閱讀 632·2021-09-02 15:41
閱讀 2048·2021-08-26 14:13
