Werden wir Helden für einen Tag

0-1 Knapsack problem #1

Posted on Mar 9, 2012 by Chung-hong Chan

假設有以下科目：

科目名稱	學分	時間
Machine Learning	10	10
Natural Language Processing	15	13
R programming	8	8
Macroeconomics	8	10

假設每科只可以報一次，而你有二十五小時的時間，應該報那些科目，才能獲得最高的學分？
這個問題，叫做 0-1 Knapsack problem 。理論上是不能用 greedy algorithm 解決的。當然，如果 constrain 是 25 小時，是可用 greedy 的。就是先是報 NLP ，得 15 學分，時間仍有 12 小時：再報最高分的 Machine Learning ，總學分是 25 ，餘下 2 小時沒有科可報。但如果 constrain 是 18 小時，是否應該根據 greedy 先報 NLP ，之後甚麼課程都報不到，只得分 15 ：還是應該報 Machine Learning + R programming ，用盡 18 小時，得分 18 ？ ((就算是用 Density , i,e, 學分 / 時間, 用 Greedy 也會是先 take NLP 。)) 似乎 Greedy 的效果不好。
另一個方法是用 Brute Force 。假設現在有個 Vector ，叫 take ，如 [1,0,0,0] 代表只 take 第一科 Machine Learning 、[1,0,1,0] 代表 take 了 Machine Learning 和 R programming 。之後試齊所有 combination of 1/0 in take ，再計算其總學分及總時間，再找出最高分時間又不超過的組合。以四科來說，那就是 16 個 combinations (2⁴)。如果是這 set data ，有 240 科的話，就是 2²⁴⁰ = 1.77 X 10⁷² 個 combinations 。假設電腦每秒可以計算 2 x 10⁹ 個 combinations (2Ghz)，那麼要計算所有 combination 就要 2.80 × 10⁵⁵ 年，也即 2.80 × 10⁴⁶ 個 gigayears 。宇宙大爆炸至今才經歷了 14 gigayears 。
有沒有更快的方法可解呢？ textbook 會講的方法叫 dynamic programming ，涉及了 divide and conquer 和 trade space for time 的概念。
例如上面的問題，數據可變成叫 credit 和 timereq 的 vector 。
另加一個 solution matrix 。此 matrix 的 column 數是時間限制 (Constrain, C) 加一， row 是 m+1 ，故 solution 是 m+1 x C+1 matrix 。上例的 constrain 是 18 小時，故此今次的 solution matrix 是 5 x 19 。另有一個一樣是 5 x 19 的 matrix ，叫做 keep 。
執行了下面的 code 之後，應該會出現以下的 solution 和 keep Matrix 。

這東西是甚麼意思呢？
直行的 0 至 18 ，是指如果你只有該時間限制，你最多可以獲得幾多學分。
橫行是指，如果科目選擇增多了，又可獲幾多學分。
None 的一行是指現在沒有任何科目可報。故此，無論你有 0 至 18 小時，都不會獲得任何學分。
至 ML 一行，代表現在只有一科 Machine Learning 可報。從此橫行可見，如果 C < 10 ，學分都是 0 分。你可想像成抄上一橫行的數字。但到了 C>= 10 ，我們可以 take Machine Learning ，故此學分變成 10 。在 keep matrix ，那些格會標示成 1 。
在 NLP 一行，代表現在除了 Machine Learning ，也可報 NLP 。當 C>=10 但 <13 時，仍是只可報 Machine Learning ，因為時間不足以報 NLP 。但是，當 C>=13 時，卻應報 NLP ，原因是 NLP 學分比單報 Machine Learning 高。
在運算 solution matrix 時，其實是另有運作的。例如 [NLP, 18] 一格，我們認為是應報 NLP ，故此分數是 15 。報完 NLP 後，時間有餘 3 小時，那 3 小時應該都應盡用。這就是 divide and conquer 的應用，即是將 problem 分成另一個細小的 subproblem ，而此些 subproblem 的結果，卻早已運算好，只要用 memoization 就可。只要看看上一橫行在 3 的位置 [ML, 3] 的最高分數是幾多，那一格是 0 ， 15 + 0 仍是 15 ，故此 [NLP, 18] 一格是 15 。
此規則在 [R Prog, 18] 一格更明顯。此一格我們比較了以下兩個數字：

不 take R Prog: 抄上一橫行的 [NLP, 18] 的 15 分
Take R Prog: 可得 8 分，餘下 10 小時。於是查上一行的 10 小時位置 [NLP, 10] ，最高分數是 10 。 10 + 8 = 18 。

對比 15 和 18 ，當然是 18 較高，故此 [R Prog, 18] 標示為 18 ， keep matrix 在此格也標示為 1 。
如是者就算出了 solution 和 keep matrices 。
solution matrix 的右下角，是最高可能獲得的分數，即是 18 。要算出是報那些科，就要看 keep matrix 。
keep matrix 也是由右下角開始看。 [Macroecon, 18] 等於 0 ，代表不應 take Macroecon ，就看上一橫行。 [R Prog, 18] 等於 1 ，代表要 take 。
當 take 了 R Prog ，時間只餘下 10 小時。故此下一回是看上一橫行的 [NLP, 10] ，此格為 0 ，代表不 take 。又看上一橫行，即 [ML, 10] 等於 1 ，代表要 take 。 take 了 ML ，時間餘下 0 小時。故此再看上一橫行的 [None, 0] 位置。 [None, 0] 是 base case ，代表計算完畢。
如此 Dynamic programming 算法，是 O(C*m) 。在 m = 4 及 C = 18 的情況，是比 Bruteforce 的 O (2^m) 更費時的。但是，只要 C 一增大，如 C>10 ， Dynamic programming 的優勢就非常明顯。例如有 240 科， C = 30 ，只需要計 7200 次，而不是 Bruteforce 的 2.80 × 10⁵⁵ 。

Sourcecode: knapsackcode