前端學習演算法2: 揹包問題 ，一步一步思考（動態規劃入門）
1 揹包問題
先舉一個很通俗易懂的例子，也是圖解演算法中的例子，有一個只能裝4kg的包，物品有音響3000元-重4kg，吉他1500元-重1kg，電腦2000元-重3kg。問，要想包裡的價值最高，應該怎麼裝？（注意：不考慮 物品的體積，不要想吉他很大放不下。）
1.1 解答
相信這個例子，隨便看一下就可以知道要裝什麼，肯定是裝電腦加吉他。總價值3500塊，又剛好4kg。
1.2 為什麼？
拜託，這麼簡單的題目，看一眼就知道為什麼了。因為其餘的組合情況，不可能比這個價值高的，即使比這個價值高，那也放不下了。很好，這就是最簡單的暴利窮舉演算法了。紅色的情況是超重了，放不下。
也就是說，物品數目是3的時候，有2^3種情況，然後找到符合條件的，也就是揹包放的下的情況，取出價值最大的組合即可。 那麼假如是4種商品呢，或者5種呢？這種組合情況是不是分別為2^4 2^5種，就很難一眼看出結果了吧，雖然上述邏輯對，但是這種 2^n 指數的量級 ，也未免也太複雜了。
2 動態規劃登場
上一篇動態規劃入門的文章裡有寫過，動態規劃，就是大事化小，小事化了。那麼對於這種型別的題目，要怎麼化繁為簡呢？要怎麼找出有代表性的模型呢？
2.1 我們來思考一下
現有揹包載重量為4kg，這個揹包已經裝了現有情況下價值最高的物品，價值為v1。那麼，在這個情況下，有一個 新的物品 ，這個物品的重量是x kg，價值是v，那麼此時對於這個4kg的包，裝物品的最大值，分幾種情況呢？
- 先來看看由於新物品的出現，這個4kg的包要怎麼裝？ 太多種情況了，但是要想裝的物品價值總和最大，那麼一定是符合接下來說的這種情況的。這裡我們不用考慮x>4的情況。
- 假如要裝這個新物品，那麼裝了後剩餘的載重量為(4-x)kg，假設這個載重量，能裝的物品最大值是v2 ，此時這個4kg的包，所能裝載的物品最大價值就是v+v2
- 假如不裝這個新物品，那4kg的包所能裝載物品的最大值還是v1。
- 所以此時的4kg包裝物品最大值是v1或者v+v2
2.2 繼續思考
- 那4-x有多少種可能呢，1kg 2kg 3kg ，由上述前提，我們已經知道了載重4kg的包能放物品最高價值是v1。而對於1kg 2kg 3kg這種簡單情況所能承載的物品最高價值，也是可以通過上述的方式去推導得出的。
3 複雜一下題目
有一個載重量是10kg 的揹包，有五個物品，a 2kg 6元，b 2kg 3元，c 6kg 5元，d 5kg 4元，e 4kg 6元。問怎麼放物品，價值最高？
根據上面的推導，我來畫一些表格
- 首先我們 只有a物品 ，然後1-10kg的包，對於只有a物品的情況，如下：解釋一下表格組成，尤其是最左邊一列，代表著依次 新有的物品 ，上面一行是承載量不同的揹包值，剩餘的是當前承載量下，對應擁有的物品的最高價值。
- 那麼此時有了 b物品（此時共有a b兩個物品可以選擇） ，想一下上面的推導的結論，填完表格，如下
結合之前推導的結論，來以2kg那一列說明一下，第一個6元，是隻有a物品時候，那麼此時能放進揹包的最高價值就是6元。當有了b物品可以選擇時，有兩種情況，（1）放進b物品，包的載重量-b物品重量後為0，然後加上b物品價值是3元（2）不放b物品原來價值是6元，取最大，即6元。
- 那麼此時有了 c物品（此時共有a b c三個物品可以選擇） ，這裡不做解釋，直接上圖
隨便抽出1個節點的值來驗證一下吧:
7kg時候，已經從abcd挑選結束，現在要考慮新增e的情況。 那個一直7kg時候，最高價值10元，新增的物品e是4kg，假如放了e，那麼剩餘空間是3kg，由圖可知，在沒有e之前，3kg的包最大能放6元物品。e的價值是6元，所以加起來12元，大於之前的最高值10元，所以對應的左標填值12元
4 程式碼實現
//by 司徒正美
function knapsack(weights, values, W){
var n = weights.length -1
var f = [[]]
for(var j = 0; j <= W; j++){
if(j < weights[0]){ //如果容量不能放下物品0的重量，那麼價值為0
f[0][j] = 0
}else{ //否則等於物體0的價值
f[0][j] = values[0]
}
}
for(var j = 0; j <= W; j++){
for(var i = 1; i <= n; i++ ){
if(!f[i]){ //建立新一行
f[i] = []
}
if(j < weights[i]){ //等於之前的最優值
f[i][j] = f[i-1][j]
}else{
f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i])
}
}
}
console.log(f)
return f[n][W]
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10)
console.log(a)
複製程式碼
最終列印的結果如下
(希望自己能一直堅持下去吧~~)
參考：
- 司徒正美文章 segmentfault.com/a/119000001…
- 演算法圖解 動態規劃一章