Algorithm筆記 9 - Knapsack演算法 (maximization problem)

問題定義

假設有個set = {(x1,y1), (x2,y2), ... (xn, yn)}，我們想要取某個subset使得其中的元素的 y值相加的和最大，前提是x值相加的和不能超過W。

x值可以只取部分，例如x1/2, x2/3, ....

以裝袋為例

一個袋子最多只能裝7個units的物體，我們有三個物體分別是(4 unit, $20), (3 unit, $18), (7 unit, $14)，試問要怎麼最大化裝入袋子的錢？

這個knapsack問題已經被證明可以用greedy algorithm找出最佳解：

其safe move就是“優先使用單位額度（$/unit)最高者”。

證明Safe move

我們還是要走過一遍證明過程，才能對以上的lemma產生信心對吧？

假設我們有一個optimal solution，裡面至少裝入某些非最高單位額度的物體X。
如果我們把袋中的X取出一單位，放入最高單位額度的物體Y的一單位，則此袋子的總體額度增加了，所以原本的optimal solution並不是optimal solution，且必定至少包含一單位的Y。

我們如果對剩下的物體們的單位一一抽換成Y，此袋子的總體額度就會繼續增加，直到所有袋子中的物體被替換完成，或是Ｙ被完全使用為止。若是後者，則次高單位額度的物體Z也遵從以上的邏輯，每次替換成Z都會增加總體額度。

得證。

演算法pseudocode和running time

上面的implementation是O(n^2)，因為外層有一個for n loop，內層要找max單位額度的時候，又要看過所有的Wi，所以是O(n)，這個很明顯有改善空間。

如果先把 vi/wi算出來並且排序(最好是O(nlogn))，就可以免去loop body中的linear search，所以knapsack algorithm最後會是O(nlogn) + O(n) = O(nlogn)。