Werden wir Helden für einen Tag

Home | About | Archive

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 (24)。如果是這 set data ,有 240 科的話,就是 2240 = 1.77 X 1072 個 combinations 。假設電腦每秒可以計算 2 x 109 個 combinations (2Ghz),那麼要計算所有 combination 就要 2.80 × 1055 年,也即 2.80 × 1046 個 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] 一格更明顯。此一格我們比較了以下兩個數字:

  1. 不 take R Prog: 抄上一橫行的 [NLP, 18] 的 15 分
  2. 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 × 1055

Sourcecode: knapsackcode


Powered by Jekyll and profdr theme