Knapsack Problem

Fractional Knapsack Problem

使用的是Greedy Algorithm，每次拿單位重量價值最高的物品直到背包負重上限為止。
假設背包上限負重8kg，現在有三樣物品a, b, c，物品不能重複拿(意思a,b,c各只有一個)，個別重量為\( (w_1,w_2,w_3)=(6, 5, 3) \)，個別價值為\( (v_1,v_2,v_3)=(8, 6, 3) \)，物品是可以分割的(意思a可分割成小塊的a_i...)，請問要怎麼拿法才能有最高獲利?

首先物品是可分割的，那每次可以拿單位重量的物品，然後只拿剩下單位重量最高的，直到拿滿負重為止。
開始計算:
這裡單位重量由kg為基準，那可以拿8個單位重量。
個別單位重量價值\( V_i, i=a,b,c \)
\( V_a = \frac{8}{6}=1.333\dots \)
\( V_b = \frac{6}{5}=1.2 \)
\( V_c = \frac{3}{3}=1 \)
則優先拿的順序為\( a\rightarrow b\rightarrow c \) ，
先拿a的6個單位重量，剩2個單位重量可負載，
接著拿b的2個單位重量，
計算價值即為最高獲利。
\( V_a\cdot 6 + V_b\cdot 2 = 8 + 2.4= 10.4 \)

0/1 Knapsack Problem

0/1意思是那個物品全不拿或全拿，
和上面可分割物品一樣，背包有負重限制，物品不能夠重複拿，和可分割不同就是不需比對單位重量的價值，用動態規劃討論拿不拿這個物品，在這重量下的最高獲利為何。

在不能分割的條件下，greedy algorithm就不能使用了。
使用Greedy Algorithm舉例:
背包負重5kg，有物品a,b,c，其重量對應為(1,2,3), 其價值對應為(60, 100, 120)。
計算單位重量為:\( V_i,\; i=\{a,b,c\} \)
\( V_a = \frac{60}{1} =60 \)
\( V_b = \frac{100}{2}=50 \)
\( V_c = \frac{120}{3}=40 \)
價值排序為
\( a> b> c \)
如果用greedy algorithm，
會先拿a，剩5-1=4kg，
再拿b，剩4-2=2kg
剩2kg不足夠負重c
所以最後拿了a、b，總價值為\( 60+100=160 \)

但最佳的拿法是b, c，總價值為\( 100+120=220 \)

0/1KP公式

\( T[i,k] \)為目前可以負重多少\( k \)，並且可以拿物品\( 1 \)到物品\( i \)的情況下，獲利最高。

假設有n種物品，背包負重最多W，不能重複拿，則
\( \{\; i \;|\; 1\leq i\leq n \;\} , \) \( \{\; k \;|\; 1\leq k\leq W \;\} \)

物品的拿法是有序性的，有n個物品，給其編號第一個為\( I_1 \)、第二個為\( I_2 \)、\( \dots \)、第n個為\( I_n \)。
\( w_i \)為\( I_i \)所需要的負重，\( v_i \)為\( I_i \)的整個價值。

一開始沒有任何東西可以拿(這裡沒有東西給他一個\( I_0 \)代替)，所以獲利都為0，可以負重0時，獲利也為0。
先討論可以從\( I_0 \)拿到\( I_1 \)的條件下，可以負重1時，最高獲利是多少，可以負重2時，最高獲利是多少，可以負重3時，最高獲利是多少，\(\dots\)，可以負重W時，最高獲利是多少，逐一填入表格。
討論可以從\( I_0 \)拿到\( I_2 \)的條件下，可以負重1時，最高獲利是多少，可以負重2時，最高獲利是多少，可以負重3時，最高獲利是多少，\(\dots\)，可以負重W時，最高獲利是多少，逐一填入表格。
\( \vdots \)
討論可以從\( I_0 \)拿到\( I_n \)的條件下，可以負重1時，最高獲利是多少，可以負重2時，最高獲利是多少，可以負重3時，最高獲利是多少，\(\dots\)，可以負重W時，最高獲利是多少，逐一填入表格。
歸納出公式為
\[ T[i,k]= \begin{cases} 0 & \text{,if } i=0, k=0 \\ T[i-1,k] & \text{,if } w_i> k \\ Max(\underline{v_i+T[i-1,k-w_i]},\;\underline{T[i-1,k]}) & \text{,if } w_i\leq k \end{cases} \] \( T[i-1,k] \)解釋:
排除當下可以拿\( I_i \)的條件下，直接查上一個從\( I_0 \)拿到\( I_{i-1} \)條件下，一樣可以負重\( k \)的獲利。

\(Max(\underline{v_i+T[i-1,k-w_i]},\;\underline{T[i-1,k]}) \) 解釋:
\( Max() \)裡有兩項，兩項都為獲利，挑最大的那個。
\( v_i+T[i-1,k-w_i] \)指現在\( I_i \)的價值+(排除\( I_i \)，然後剩下\( k-w_i \)的負重下的獲利)。

開始填表

\( \{ I_i \;|\; 0\leq i\leq 3\} \) 這一column指的是現在有什麼物品可以選來放在背包。
\( \{ I_0=\emptyset,\;I_1=a,\; I_2=b,\;I_3=c \} \)
\( I_i \)為當下如果拿這個物品來放的討論
\( k \)為現在可以負重多少
經公式由左至右, 由上到下填表
灰色部分為預設值。
可以多新增一些參數去記住討論的結果，方便日後回推內容。(上面公式只有表示最高價值的數值，並沒有紀錄背包內容有什麼)。
白色框內說明: 上面為現在背包內放了什麼,下面為背包內總價值。
\( \{ I_i \;|\; 0\leq i\leq 3\} \) \( I_i \)\ \( k \) 0 1 2 3 4 5
\( \{ \} \) \( I_0 \) 0 0 0 0 0 0
\( \{ a \} \) \( I_1 \) 0 \( \{ a \} \)
\( 60 \) 		\( \{ a \} \)
\( 60 \) 		\( \{ a \} \)
\( 60 \) 		\( \{ a \} \)
\( 60 \) 		\( \{ a \} \)
\( 60 \)
\( \{ a,b \} \) \( I_2 \) 0 \( \{ a \} \)
\( 60 \) 		\( \{ b \} \)
\( 100 \) 		\( \{ a,b \} \)
\( 160 \) 		\( \{ a,b \} \)
\( 160 \) 		\( \{ a,b \} \)
\( 160 \)
\( \{ a,b,c \} \) \( I_3 \) 0 \( \{ a \} \)
\( 60 \) 		\( \{ b \} \)
\( 100 \) 		\( \{ a,b \} \)
\( 160 \) 		\( \{ a,c \} \)
\( 180 \) 		\( \{ b,c \} \)
\( 220 \)
最後在最右下角的格子可以得知，拿b,c可以到最高價值。