ADA 6.5: Knapsack Problem 背包問題

###### tags: `ADA 6.5` # ADA 6.5: Knapsack Problem 背包問題 ## 前言 * Input：n items where $i$-th item has value $v_i$ and weighs $w_i$ ($v_i$ and $w_i$ are positive integers) * Output：the ++maximum value++ for the knapsack with capacity of $W$ >**猴子中文翻譯** > Input 就是他有 n 個 items(有n個東西你可以選擇要不要裝進去)，每個 item 都有它的 value $v_i$ 和他的 weighs $w_i$ （可以想像 value 是價值，weighs 是重量） > 我們要讓 value 也就是包包裡面裝了越多價值的東西越好，但是我們包包會有它的限制就是 $W$ ![網路偷圖](https://i.imgur.com/cOeRwU2.png) * Variants of knapsack problem 變形背包問題 * [0-1 Knapsack Problem](#0-1-Knapsack-Problem) (每項物品只能拿一個 EX: 拿 or 不拿) * [Unbounded Knapsack Problem](#Unbounded-Knapsack-Problem) (每項物品可以重複拿很多個) * [Multidimensional Knapsack Problem](#Multidimensional-Knapsack-Problem) (背包空間有限 $W$) * [Multiple-Choice Knapsack Problem](#Multiple-Choice-Knapsack-Problem) (每一類物品最多拿一個) * [Fractional Knapsack Problem](#Fractional-Knapsack-Problem) (物品可以只拿部分 EX: 可以切一半的東西我只拿一半 0.5 之類的) --- ## 0-1 Knapsack Problem :::info Input: $n$ items where $i$-th item has value $v_i$ and weighs $w_i$ Output: the max value within $W$ capacity, where each item is chosen **at most once** ::: 不拿物品，或是只拿一個的狀況。 ### Step 1: Characterize an OPT Solution * Subproblems ==ZO-KP($i, w$)== * ZO-KP($i, w$): 0-1 knapsack proble within $w$ capacity for the first $i$ items ==考慮 $i$ items 然後 capacity 剩下 $w$ 的狀況== `這句我反覆咀嚼，好像懂了又好像沒有懂` `Andy: 假設你可以背10kg，拿了一個3kg的水，剩下7kg的預算還可以使用。這裡的3kg就是w` * Goal: ZO-KP($n, W$) ==目標就是要找到這個 n 和 W 的值== `這裡的Ｗ和上面 w 有什麼不一樣？` `Andy:承上題 W = (w == 10kg)` * Optimal substructure: suppose OPT is an optimal solution to ZO-KP(i, w), there are 2 cases:(拿跟不拿的 case) * Case 1: item $i$ in OPT * OPT\{$i$} is an optimal solution of ZO-KP(i - 1, w - w_i) :::warning $M_{i,w}$ = $v_i$ + $M_{i-1, w-w_i}$ ::: * Case 2: item $i$ not in OPT * OPT is an optimal solution of ZO-KP(i - 1, w ) :::warning $M_{i,w}$ = $M_{i-1, w}$ ::: ### Step 2: Recursively Define the Value of an OPT Solution * Recursively define the value :::warning $$ M_{i,w}= \begin{cases} 0, &\text {if $i$=0} \\ M_{i-1,w}, &\text {if $w_i$ > $w$} \\ max([v_i + M_{i-1, w-w_i}] , M_{i-1, w}), &\text {otherwise} \end{cases} $$ ::: ### Step 3: Compute Value of an OPT Solution :::success item List |$i$|$w_i$|$v_i$| |---|-----|-----| |1|1|4| |2|2|9| |3|4|20| $W$ = 5 table: |i\w|0|1|2|3|4|5| |-|-|-|-|-|-|-| |0|0|0|0|0|0|0| |1|0|4|4|4|4|4| |2|0|4|9|13|13|13| |3|0|4|9|13|20|24| ::: ## Unbounded Knapsack Problem :::info Input: $n$ items where $i$-th item has value $v_i$ and weighs $w_i$ has **unlimted supplies** Output: the max value within $W$ capacity ::: 沒有限制可以拿幾個物品的狀況。 ### Step 1: Characterize an OPT Solution * Subproblems * ~~U-KP($i$, $w$)~~: ~~unbounded knapsack proble within $w$ capacity for the first $i$ items~~ * ~~Goal:~~ ~~U-KP($n$, $W$)~~ ==Time complexity = $\Theta(n^2W)$, not a good solution.== ==因為不用再考慮拿過不能再拿的狀況== ==所以就不用再考慮 $i$== * U-KP($w$): unbounded knapsack proble within $w$ capacity for the first $i$ items * Goal:U-KP($W$) * Optimal substructure: suppose OPT is an optimal solution to U-KP($w$), there are n cases: * Case 1: item $1$ in OPT * Removing an item 1 from OPT is an optimal solution of U-KP($w - w_1$) * Case 2: item $2$ in OPT * Removing an item 2 fromOPT is an optimal solution of U-KP($w-w_2$) * ... * Case n: item $n$ in OPT :::warning $M_w = v_i + M_{w-w_i}$ ::: ### Step 2: Recursively Define the Value of an OPT Solution * Recursively define the value :::warning $$ M_{i,w}= \begin{cases} 0, &\text {if $w$=0 or $w_i>w$ for all $i$} \\ max_{(1 \leq i \leq n,w_i \leq w)}(v_i + M_{w-w_i}), &\text {otherwise} \end{cases} $$ ::: ### Step 3: Compute Value of an OPT Solution :::success item List |$i$|$w_i$|$v_i$| |---|-----|-----| |1|1|4| |2|2|9| |3|4|17| $W$ = 5 table: |$w$|0|1|2|3|4|5| |-|-|-|-|-|-|-| |$M[w]$|0|4|9|13|18|22| $w_1=max(4+0)$ $w_2=max(4+4,9+0)$ $w_3=max(4+9,9+4)$ $w_4=max(4+13,9+9,17+0)$ $w_5=max(4+18,9+13,17+4)$ ::: ## Multidimensional Knapsack Problem :::info Input: $n$ items where $i$-th item has value $v_i$ and weighs $w_i$ and size $d_i$ Output: the max value within $W$ capacity and with the size of $D$, where each item is chosen at most once ::: ### Step 1: Characterize an OPT Solution * Subproblems * M-KP($i, w, d$): multidimensional knapsack proble within $w$ capacity and $d$ size for the first $i$ items * Goal: M-KP($n, W, D$) * Optimal substructure: suppose OPT is an optimal solution to M-KP($i, w, d$), there are 2 cases: * Case 1: item $i$ in OPT * OPT\{$i$} is an optimal solution of M-KP($i-1, w-w_i, d-d_i$) * Case 2: item $i$ not in OPT * OPT is an optimal solution of M-KP($i-1, w,d$) ### Step 2: Recursively Define the Value of an OPT Solution * Recursively define the value :::warning $$ M_{i,w}= \begin{cases} 0, &\text {if $i$=0} \\ M_{i-1,w,d}, &\text {if $w_i>w$ or $d_i>d$} \\ max([v_i + M_{i-1, w-w_i, d-d_i}] , M_{i-1, w,d}), &\text {otherwise} \end{cases} $$ ::: ### Step 3: Compute Value of an OPT Solution :::success item List |$i$|$w_i$|$v_i$|$d_i$| |---|-----|-----|-----| |1|1|4|2| |2|2|9|4| |3|4|20|1| $W$ = 4 $D$ = 6 table: $d$ = 0 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|0|0|0|0| |2|0|0|0|0|0| |3|0|0|0|0|0| $d$ = 1 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|0|0|0|0| |2|0|0|0|0|0| |3|0|0|0|0|20| $d$ = 2 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|4|4|4|4| |2|0|4|4|4|4| |3|0|4|4|4|20| $d$ = 3 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|4|4|4|4| |2|0|4|4|4|4| |3|0|4|4|4|20| $d$ = 4 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|4|4|4|4| |2|0|4|9|9|9| |3|0|4|9|9|20| $d$ = 5 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|4|4|4|4| |2|0|4|9|9|9| |3|0|4|9|9|20| $d$ = 6 |i\w|0|1|2|3|4| |---|-|-|-|-|-| |0|0|0|0|0|0| |1|0|4|4|4|4| |2|0|4|9|13|13| |3|0|4|9|13|20| ::: ## Multiple-Choice Knapsack Problem :::info Input: $n$ items * $v_{i,j}$: value of $j$-th item in the group $i$ * $w_{i,j}$: weight of $j$-th item in the group $i$ * $n_{i}$: number of items in group $i$ * $n$: total number of items $( \Sigma n_i )$ * $G$: total number of groups Output: the maximum value for the knapsack with capacity of $W$, where **the item from each group can be selected at most once** ::: 一個群組只能拿一個的狀況 ### Step 1: Characterize an OPT Solution * Subproblems * ~~MC-KP($w$)~~: ~~$w$ capacity~~ * MC-KP($i,w$): $w$ capacity for the first $i$ groups * ~~MC-KP($i,j,w$)~~: ~~$w$ capacity for the first *j* items from first $i$ groups~~ * Goal: MC-KP($G, W$) * Optimal substructure: suppose OPT is an optimal solution to MC-KP($i, w$), for the group $i$, there are $n_i + 1$ cases: * Case 1: no item from $i$-th group in OPT * OPT\{$i$} is an optimal solution of MC-KP($i-1, w$) * Case j+2: $j$-th item from $i$-th group ($item_{i,j}$) in OPT * OPT ($item_{i,j}$) is an optimal solution of MC-KP($i-1, w-w_{i,j}$) ### Step 2: Recursively Define the Value of an OPT Solution * Recursively define the value :::warning $$ M_{i,w}= \begin{cases} 0, &\text {if $i$=0} \\ M_{i-1,w}, &\text {if $w_{i,j}>w$ for all $jd$} \\ max_{1 \leq j \leq n_i}([v_{i,j} + M_{i-1, w-w_{i,j}}] , M_{i-1, w}), &\text {otherwise} \end{cases} $$ ::: ### Step 3: Compute Value of an OPT Solution :::warning 這題老師就沒有舉例了 ::: :::info 複雜度計算蠻有趣的，所以就記下來了。 $$ \sum_{i=1}^G \sum_{w=0}^W \sum_{j=1}^{n_i} c=c \sum_{w=0}^W \sum_{i=1}^G \sum_{j=1}^{n_i} 1=c \sum_{w=0}^W n=cnW $$ $$ \Downarrow $$ $$ T(n) = \Theta(nW) $$ ::: ## Fractional Knapsack Problem :::info 可以隨便分割物品的狀況 ::: ==簡單到我就不做筆記了== :::danger 找到CP值最高的那個物品，就拿到滿就好了 :::