一個晚上 小偷闖了空門
眼前有五件寶物 價值和重量如下
但是小偷背包不夠塞 最多只能帶11公斤的寶物走
那這樣要怎麼帶才能利益最大化呢?
我們可以用動態規劃來解決
小問題被解決後可以組合成為大問題的解
公式如下
i = 能偷的寶物數量
W = 背包剩餘容量
m() 為 最佳利益
wi = 決定偷的那件寶物重量
vi = 決定偷的那件寶物價值
因為背包容量有限
我們在決定要不要偷寶物時有兩條路
選擇偷 vi + m(i - 1, W - wi)
或是不偷 m(i - 1, W)
看哪個利益比較大就走那條路
奇怪 偷不是一定比沒偷利益還多嗎?
沒有哦 如果因為偷了這件
導致背包容量塞不下其他寶物
有可能總價值被其他組合反超!
===進入例子===
為了方便理解 建立一個二維陣列
0 1 2 3 4 5 6 7 8 9 10 11 (W:背包裝載重量 最多到11公斤)
0
1
2
3
4
5
(i:能偷幾樣 最多五樣)
陣列中放的是條件下的最佳解(最大利益)
我們先從第一個row i = 0開始吧
假設小偷 可以偷0樣寶物
那這樣不管背包再大也沒用 不能偷沒利益
所以m[0][0 to 11]都是0
0 1 2 3 4 5 6 7 8 9 10 11 (W:背包能裝重量 最多到11公斤)
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1
2
3
4
5
(i:能偷幾樣 最多五樣)
再來 i = 1 可以偷一件寶物
第一件寶物為(w = 1, v = 1)
假設背包能裝 0 公斤 意思就是背包不能裝東西 m[1][0] = 0
假設背包能裝 1 公斤 發現剛好第一個寶物就是1公斤
決定要不要偷 套用公式:
選擇偷 m(i - 1, W - wi) + vi => m[0][1 - 1] + 1 = m[0][0] + 1 = 1
或是不偷 m(i - 1, W) => m[0][1] = 0
兩個比較看誰大 => 1 > 0
所以我們應該偷 => m[1][1] = 1
在背包空間1、可以偷1件寶物時最佳解為1
剩下的m[1][2 to 11] 因為只能偷一件寶物 所以即使背包再大 最大利益都是1
0 1 2 3 4 5 6 7 8 9 10 11 (W:背包能裝重量 最多到11公斤)
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1
2
3
4
5
(i:能偷幾樣 最多五樣)
再來 i = 2 可以偷兩件寶物
第二件寶物為(w = 2, v = 6)
m[2][0] = 0
m[2][1] 因為背包不夠塞第二件所以最佳解跟m[1][1]一樣 = 1
m[2][2] 可以塞第二件寶物了 套公式
偷 m[2 - 1][0] = m[1][0] + 6 = 6
不偷 m[2 - 1][2] =m[1][2] = 1 所以決定偷 m[2][2] = 6
在背包空間2、可以偷2件寶物時最佳解為6
m[2][3] 背包有空間可以塞寶物1和寶物2 m[2][3] = 7
在背包空間3、可以偷2件寶物時最佳解為7
剩下背包再大因為只能塞兩件寶物所以結果都一樣
m[2][4 to 11] = 7
0 1 2 3 4 5 6 7 8 9 10 11 (W:背包能裝重量 最多到11公斤)
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1
2 0 1 6 7 7 7 7 7 7 7 7 7 7
3
4
5
(i:能偷幾樣 最多五樣)
再來 i = 3 可以偷三件寶物
第三件寶物為(w = 5, v = 18)
m[3][0] = 0
m[3][1 to 4] 因為背包塞不下第三件寶物
所以最佳解跟m[2][1 to 4]一樣
0 1 2 3 4 5 6 7 8 9 10 11 (W:背包能裝重量 最多到11公斤)
0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1
2 0 1 6 7 7 7 7 7 7 7 7 7 7
3 0 1 6 7 7
4
5
(i:能偷幾樣 最多五樣)
但是到m[3][5]的時候 小偷發現背包空間夠塞寶物三了
=> 決定要偷還是不偷
偷m[2][0] + 18 = 18
不偷m[2][5] = 7 所以決定偷 m[3][5] = 18
在背包空間5、可以偷3件寶物時最佳解為18
.
.
.
.
以此類推 帶公式比大小決定偷與不偷
可以得到 在背包空間11(max)、可以偷5件寶物(max)時的最佳解
也就是一開始要算的答案
reference: https://zhuanlan.zhihu.com/p/30959069
完
創作內容
動態規劃 背包問題
☆活動☆ (32)