[LIOJ]Knapsack Problem, Dynamic programming, 0/1 背包問題

總算是解開了,來說說我這題的解題過程。

Accepted

首先我想把物品用 CP 值排序,價值高重量輕的優先放進去,但馬上碰到問題了,例如:與其放一件 CP 值高但再也放不下其他東西的物品,不如放兩件 CP 值低的物品,背包總價值反而會提高,這樣用 CP 值排序就無用了。

再來我想用暴力破解法,把全部物品組合列出來、篩掉放不進背包的組合,最後找出價值最高的組合,照理說應該是可行的(?),只是時間複雜度很高。
果不其然 Time Limit Exceeded (還多試了幾次試圖蒙混過關)。

GG

放棄暴力破解之後我 Google 了 "背包問題" ,得到新的關鍵字 "動態規劃" (Dynamic programming)。起初真的是完全不知道在幹嘛,沒一篇文章看得懂,卡了好幾個禮拜…最後找到這篇,雖然是來自內容農場,但是真的幫助到我 XD。

這時我注意到一件很詭異的事…我現在看得懂之前那些教學文章了 。
欸不是,我都會了還看教學文幹嘛?這種東西不是應該給不會的人看得嗎?(American-chopper.jpg)
在查文章的當下我就默默心想要是我會了這題之後一定要寫一篇超級淺顯易懂、連我的看得懂的攻略文…以下開始解題吧:

首先解釋一下 "動態規劃" 大概是在幹嘛。

American-chopper.jpg

針對那些無法一步到位的目標 (找到工作),我們藉由達成小的目標 (例如:乖乖上學不要翹課、學習工作所需技能、做作品、拜託朋友內推…),來一步步增加我們找到工作的機率。解題目相對找工作來說又簡單一些,只要前面步驟對了,最後我們一定可以得到正確答案。

那麼背包問題要怎麼拆解步驟呢?首先我們先確定一件事:如果有件東西放進背包會增加背包的總價值,那我們就把那東西放進來,但其實你放進來的不只有那東西,還有扣掉那東西的重量後,"剩餘背包空間的價值"。

用文字來描述該不該放這東西就是:
如果 目前背包物品組合總價值 < 下個物品的價值 + 剩餘背包空間的最佳解

我們就將目前背包的東西倒出來,用新的東西以及之前算出來的最佳組合替換。

換個角度來舉例,我們應不應該跟現在的男/女朋友結婚呢?
先假設我們已經有了男/女朋友。
一個衡量價值的單位,叫做幸福度好了。
當前狀態叫做 "交往中",幸福度 60。下個狀態叫做 "結婚後",幸福度 80。

如果只看兩個狀態來選擇(80>60),很明顯我們應該要去結婚。

但是事情沒有那麼簡單嘛,結婚後你得負擔更多責任,生活可能會更有目標,更有動力努力打拼。但同時如果生了小孩,你下班後就得顧囝仔,再也不能回到家就打電動看動畫科科笑。
所以說,要不要結婚的公式應該更新成這樣:

如果 "結婚後"的幸福度 + "結婚後的其他影響" > "交往中"的幸福度

我們就選擇結婚,不然就維持現狀。

所以重點來了,我們目前已知交往中的幸福度以及結婚後的幸福度,唯一不確定的因素就是那個 "結婚後的其他影響",只要搞清楚那些影響,就能決定要不要結婚。

繞了一大圈,總算是回到背包問題,藉由結婚例子修改這一行:

下個物品的價值(結婚後) + 剩餘背包空間的最佳解(其他影響) >
目前背包物品組合總價值(交往中)

也就是說,我們只要知道 "剩餘背包空間的最佳解",就能知道該不該改放新的物品組合。寫成公式就是這樣:

http://www.csie.ntnu.edu.tw/~u91029/KnapsackProblem.html

制定好決策方式,終於可以來偷東西了。物品清單如下:
item_A : 價值 100 ; 重量 9
item_B : 價值 60; 重量 5
item_A : 價值 70; 重量 2
背包能承受的總重量為 10

很多文章講到這裡就開始列表格了,我覺得這正是我當初看不懂的原因,所以我想在這裡做一點小變動,直接來帶入公式就會知道為什麼要列表。
類似這種表格:

來源:https://openhome.cc/Gossip/AlgorithmGossip/KnapsackProblem.htm

首先我們來決定要不要放 A 物品,按照公式:

物品組合總價(未知) vs
物品 A 價值(100) + 剩餘負重 1 (最大負重 - 物品A負重)的最佳解(未知)

當前物品組合總價我們可以假設此時背包剩餘負重是 10 且沒有物品可以偷的情況,此時的最大價值就是 0 (沒東西可以偷嘛),因此在這裡不管剩餘負重 1 的背包價值為何,選擇偷 A 物品都會是最好選擇。

當前物品組合總價(0) < 物品 A 價值 (100) + 剩餘負重 1 的最佳解(未知)

結論:要放 A ,我們將放入 A +剩餘負重 1 的背包做為新的比較基準。

再來決定要不要放 B 物品:

物品 A 價值 (100) + 剩餘負重 1 的最佳解 (未知) vs
物品 B 價值 (60) + 剩餘負重 5 的最佳解 (未知)

看到這裡,應該就能明白為什麼要列表了。在這裡儘管知道物品 A, B 的價值,但由於兩邊都有未知數,我們無法確定到底哪邊的價值高,因此會需要找出各種負重下的背包最佳解,也就是從 0 負重 (個人偏好,程式碼比較好寫XD) 的背包開始找最佳解,直到最大負重 10 的背包。來開始列表吧!

充滿溫度ㄉ手作表格

首先我們初始化無物品時各種負重下的最佳解,方便我們之後做比較。
下一步開始考慮有 A 物品的情況。

野生的 A 物品出現了

箭頭起點就是我們的比較基準(0 物品, 負重上限 0),之後每一格都是這樣比較,比較方法也就是前面一直再提的公式:

當前負重最佳解(0) vs A 物品價值 (100) + 剩餘負重 -9 的最佳解 (0)
但由於物品負重 > 當前負重上限,一旦放入 A 物品背包就爆了,所以只能保持之前的最佳解。

一格一格重複同樣的比較,直到負重上限 10。

來看到有變化的部分,在負重 9 的時候是這樣的:

當前負重最佳解(0) vs A 物品價值(100)+ 剩餘負重 0 的最佳解(0)

剩餘負重 0 的最佳解我們剛剛初始化時已經找出來了,也就是 0 。
0 < 100 + 0,所以我們將目前負重(9)的最佳解更新成 100。

在來看到負重 10 的情況:

當前負重最佳解(0) vs A 物品價值(100) + 剩餘負重 1 的最佳解(0)

剩餘負重 1 的最佳解我們剛剛初始化時已經找出來了,是 0 。
0 < 100 + 0,所以我們將目前負重(10)的最佳解更新成 100。

野生的 B 物品也出現了!

新增 B 物品也是依樣畫葫蘆,只是我們的比較基準從初始化那行移動到 A(100 ,9) 那行,之後新增 C 物品也是一樣,把比較基準移動到 B(60, 5) 行。
在負重 0~4 都沒變化,因為都放不下 B 物品,所以維持之前的最佳解(0)。

直到負重 5 ,這時候的公式是這樣的:

當前負重最佳解 (0) vs B 物品價值(60) + 剩餘負重 0 的最佳解(0)
0 < 60 + 0,所以我們將目前負重(5)的最佳解更新成 60。

B 物品也判斷完了

來看到負重 9 的情況:

當前負重最佳解 (100) vs A 物品價值(60) + 剩餘負重 5 的最佳解(0)

剩餘負重 5 的最佳解我們剛剛找出來了,是 0 。
100 > 60 + 0,所以我們維持之前的最佳解 (100)。

物品 C 姍姍來遲

來看到負重 2 的情況:

當前負重最佳解 (0) vs C 物品價值(70) + 剩餘負重 0 的最佳解(0)

剩餘負重 0 的最佳解我們剛剛已經找出來了,是 0 。
0 < 70 + 0,所以我們將目前負重(2)的最佳解更新成 70。

持續做一樣的比較

來看到負重 5 的情況:

當前負重最佳解 (60) vs C 物品價值(70) + 剩餘負重 3 的最佳解(0)

剩餘負重 3 的最佳解我們剛剛已經找出來了,是 0 。
60 < 70 + 0,所以我們將目前負重(5)的最佳解更新成 70。

再來看到負重 7 的情況:

當前負重最佳解 (60) vs C 物品價值(70) + 剩餘負重 5 的最佳解(60)

剩餘負重 5 的最佳解我們剛剛已經找出來了,是 60 。
60 < 70 + 60,所以我們將目前負重(7)的最佳解更新成 130。

填完表的同時,代表答案也出來了。

來看到負重 10 的情況:

當前負重最佳解 (100) vs C 物品價值(70) + 剩餘負重 8 的最佳解(60)

剩餘負重 8 的最佳解我們剛剛已經找出來了,是 60 。
100 < 70 + 60,所以我們將目前負重(10)的最佳解更新成 130。
算到這裡,所有物品都考慮完了,答案也就出來了,最後回傳答案即可。
最後把上面那些繁複的步驟丟給程式處理即可!