# Knapsack - 背包問題 在一次搶珠寶店的過程中，搶劫犯只能搶走以下三種珠寶，其重量和價值如下表所述。 | Item(jewellery) | Weight | Value | |-----|-----|-----| | 1 | 6 | 23 | | 2 | 3 | 13 | | 3 | 4 | 11 | 搶劫犯這次過來光顧珠寶店只帶了一個最多只能承重17 kg的粉紅色小包，于是問題來了，怎樣搭配這些不同重量不同價值的珠寶才能不虛此行呢？哎，這年頭搶劫也不容易啊... 用數學語言來描述這個問題就是：背包最多只能承重 WWW kg, 有 nnn 種珠寶可供選擇，這 nnn 種珠寶的重量分別為 ω1,?,ωn\omega_1,\cdots,\omega_nω1,?,ωn, 相應的價值為 v1,?,vnv_1,\cdots,v_nv1,?,vn. 問如何選擇這些珠寶使得放進包里的珠寶價值最大化？ ### Knapsack with repetition - 物品重復可用的背包問題 由于這類背包問題中，同一物品可以被多次選擇，因此稱為Knapsack with repetition, 又稱Unbounded knapsack problem(無界背包問題). 動態規劃是解決背包問題的有力武器，而在動態規劃中，主要的問題之一就是——狀態(子問題)是什么？在本題中我們可以從兩個方面對原始問題進行化大為小：要么是是更小的背包容量 ω≤W\omega \leq Wω≤W, 要么嘗試更少的珠寶數目(如珠寶 1,2,?,j,?for?j≤n1, 2, \cdots , j, ~for~ j \leq n1,2,?,j,?for?j≤n). 這兩個狀態(子問題)究竟哪個對于解題更為方便，還需進一步論證——能否根據狀態(子問題)很方便地寫出狀態轉移方程。 先來看看第一種狀態：**在背包容量為 ω\omegaω 時搶劫犯所能獲得的最優值為 K(ω)K(\omega)K(ω).** 對應此狀態的狀態轉移方程并不是那么直觀，先從 K(ω)K(\omega)K(ω) 所包含的信息出發，K(ω)>0K(\omega) > 0K(ω)>0 時，背包中必然含有某件值錢的珠寶，不妨假設最優值 K(ω)K(\omega)K(ω) 包含某珠寶 iii, 那么將珠寶 iii 從背包中移除后，背包中剩余珠寶的價值加上珠寶 iii 的價值即為 K(ω)K(\omega)K(ω). 哪尼？這不就是個天然的狀態轉移方程么？搶劫犯靈機一動，立馬想出了如下狀態轉移方程：K(ω)=F(ω?ωi)+vi?(ωi∈Ω)K(\omega) = F(\omega - \omega_i) + v_i ~(\omega_i \in \Omega)K(ω)=F(ω?ωi)+vi?(ωi∈Ω) 其中 F(ω?ωi)F(\omega - \omega_i)F(ω?ωi) 為拿出珠寶 iii 后的價值映射函數(用人話來說就是把粉紅色小包里剩下的珠寶價值加起來)，取出來的珠寶重量 ωi<ω\omega_i < \omegaωi<ω(總不能取出大于背包重量的珠寶吧...), Ω\OmegaΩ 即為 K(ω)K(\omega)K(ω) 中 ωi\omega_iωi 的所有可能取值。想了想好像哪里不對勁，K(ω)K(\omega)K(ω) 的轉移關系沒鼓搗出來，反而新添了個 F(ω?ωi)F(\omega - \omega_i)F(ω?ωi), 真是舊愛未了又添新歡... 別急，再仔細瞅瞅以上等式兩端，拿出珠寶 iii 后，其價值 viv_ivi 就可以認為是一個定值了，故要想 K(ω)K(\omega)K(ω) 為最大值，F(ω?ωi)F(\omega - \omega_i)F(ω?ωi) 也理應是背包容量為 ω?ωi\omega - \omega_iω?ωi 時的包內珠寶的最大價值，如若不是，則必然存在 F(ω?ωi)<K(ω?ωi)F(\omega - \omega_i) < K(\omega - \omega_i)F(ω?ωi)<K(ω?ωi), 即有K(ω)=F(ω?ωi)+vi<K(ω?ωi)+vi=K′(ω)K(\omega) = F(\omega - \omega_i) + v_i < K(\omega - \omega_i) + v_i = K^{\prime}(\omega)K(ω)=F(ω?ωi)+vi<K(ω?ωi)+vi=K′(ω)與 K(ω)K(\omega)K(ω) 為在背包容量為 ω\omegaω 時的最大值的定義不符，故假設不成立，F(ω?ωi)=K(ω?ωi)F(\omega - \omega_i) = K(\omega - \omega_i)F(ω?ωi)=K(ω?ωi). 千斤頂終于成功上位——變成了備胎... 新的狀態轉移方程可改寫為：K(ω)=K(ω?ωi)+viK(\omega) = K(\omega - \omega_i) + v_iK(ω)=K(ω?ωi)+vi 嗯，好像還是有哪里不對勁，千斤頂雖然已晉級為備胎，可備胎這個身份實在是不怎么好聽，這不還有下標 iii 這個標記嘛，我們給搶劫犯想想法子，怎么才能讓備胎盡快轉正呢？！仔細分析發現我們剛才取出d的價值 viv_ivi 是從已知背包容量為 ω\omegaω 時取出來的珠寶 iii, 重量為 ωi\omega_iωi. 那么到底那幾個珠寶才是可能被取出來的呢？答案不得而知，只知道肯定是小于背包容量 ω\omegaω 中的某一個。既然是這樣，我們把所有小于背包容量 ω\omegaω 的珠寶挨個拿出來比一比不就完了么？但這樣一來又有了新的問題：取出來的珠寶 ωi\omega_iωi 不一定是最大值 K(ω)K(\omega)K(ω)中所包含的珠寶，那假如我們一定要拿出來比一比呢？得到的結果自然是不大于最大值 K(ω)K(\omega)K(ω)(如果不是，反證法證之), 用數學語言表示就是：K(ω)≥K(ω?ωj)+vj?(ωj?Ω)K(\omega) \geq K(\omega - \omega_j) + v_j ~(\omega_j \notin \Omega)K(ω)≥K(ω?ωj)+vj?(ωj?Ω) 整理一下思路，用優雅的數學語言來表示就是：K(ω)=maxi:?ωi≤ω{K(ω?ωi)+vi}K(\omega) = \max_{i:~\omega_i \leq \omega} \{K(\omega - \omega_i) + v_i\}K(ω)=maxi:?ωi≤ω{K(ω?ωi)+vi} 備胎終于得以登堂入室，警察叔叔，就是她了... 狀態轉移方程終于完整的找到了，千斤頂竊喜道：皇天不負有心人，我也有轉正的一天，蛤蛤蛤... 令`dp[i + 1][j]`表示從前`i`種物品中選出總重量不超過`j`時總價值的最大值。那么有轉移方程： ~~~ dp[i + 1][j] = max{dp[i][j - k × w[i]] + k × v[i] | 0 ≤ k} ~~~ 最壞情況下時間復雜度為 O(kW2)O(kW^2)O(kW2). 對上式進一步變形可得： ~~~ dp[i + 1][j] = max{dp[i][j - k × w[i]] + k × v[i] | 0 ≤ k} = max{dp[i][j], max{dp[i][j - k × w[i]] + k × v[i] | 1 ≤ k}} = max{dp[i][j], max{dp[i][(j - w[i]) - k × w[i]] + k × v[i] | 0 ≤ k} + v[i]} = max{dp[i][j], dp[i + 1][j - w[i]] + v[j]} ~~~ **注意等式最后一行，咋看和01背包一樣，實際上區別在于`dp[i + 1][]`, 01背包中為`dp[i][]`.** 此時時間復雜度簡化為 O(nW)O(nW)O(nW). ### Knapsack without repetition - 01背包問題 上節講述的是最原始的背包問題，這節我們探討條件受限情況下的背包問題。若一件珠寶最多只能帶走一件，請問現在搶劫犯該如何做才能使得背包中的珠寶價值總價最大？ 顯然，無界背包中的狀態及狀態方程已經不適用于01背包問題，那么我們來比較這兩個問題的不同之處，無界背包問題中同一物品可以使用多次，而01背包問題中一個背包僅可使用一次，區別就在這里。我們將 K(ω)K(\omega)K(ω) 改為 K(i,ω)K(i,\omega)K(i,ω) 即可，**新的狀態表示前 iii 件物品放入一個容量為 ω\omegaω 的背包可以獲得的最大價值。** 現在從以上狀態定義出發尋找相應的狀態轉移方程。K(i?1,ω)K(i-1, \omega)K(i?1,ω)為 K(i,ω)K(i, \omega)K(i,ω) 的子問題，如果不放第 iii 件物品，那么問題即轉化為「前 i?1i-1i?1 件物品放入容量為 ω\omegaω 的背包」，此時背包內獲得的總價值為 K(i?1,ω)K(i-1, \omega)K(i?1,ω)；如果放入第 iii 件物品，那么問題即轉化為「前 i?1i-1i?1 件物品放入容量為 ω?ωi\omega - \omega_iω?ωi 的背包」，此時背包內獲得的總價值為 K(i?1,ω?ωi)+viK(i-1, \omega - \omega_i) + v_iK(i?1,ω?ωi)+vi. 新的狀態轉移方程用數學語言來表述即為：K(i,ω)=max{K(i?1,ω),K(i?1,ω?ωi)+vi}K(i,\omega) = \max \{K(i-1, \omega), K(i-1, \omega - \omega_i) + v_i\}K(i,ω)=max{K(i?1,ω),K(i?1,ω?ωi)+vi} 這里的分析是以容量遞推的，但是在容量特別大時，我們可能需要以價值作為轉移方程。定義狀態`dp[i + 1][j]`為前`i`個物品中挑選出價值總和為`j` 時總重量的最小值（所以對于不滿足條件的索引應該用充分大的值而不是最大值替代，防止溢出）。相應的轉移方程為：前`i - 1` 個物品價值為`j`, 要么為`j - v[i]`(選中第`i`個物品). 即`dp[i + 1][j] = min{dp[i][j], dp[i][j - v[i]] + w[i]}`. 最終返回結果為`dp[n][j] ≤ W` 中最大的 j. ### 擴展 以上我們只是求得了最終的最大獲利，假如還需要輸出選擇了哪些項如何破？ 以普通的01背包為例，如果某元素被選中，那么其必然滿足`w[i] > j`且大于之前的`dp[i][j]`, 這還只是充分條件，因為有可能被后面的元素代替。保險起見，我們需要跟蹤所有可能滿足條件的項，然后反向計算有可能滿足條件的元素，有可能最終輸出不止一項。 ### Java ~~~ import java.util.*; public class Backpack { // 01 backpack with small datasets(O(nW), W is small) public static int backpack(int W, int[] w, int[] v, boolean[] itemTake) { int N = w.length; int[][] dp = new int[N + 1][W + 1]; boolean[][] matrix = new boolean[N + 1][W + 1]; for (int i = 0; i < N; i++) { for (int j = 0; j <= W; j++) { if (w[i] > j) { // backpack cannot hold w[i] dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]); // pick item i and get value j matrix[i][j] = (dp[i][j - w[i]] + v[i] > dp[i][j]); } } } // determine which items to take for (int i = N - 1, j = W; i >= 0; i--) { if (matrix[i][j]) { itemTake[i] = true; j -= w[i]; } else { itemTake[i] = false; } } return dp[N][W]; } // 01 backpack with big datasets(O(n\sigma{v}), W is very big) public static int backpack2(int W, int[] w, int[] v) { int N = w.length; // sum of value array int V = 0; for (int i : v) { V += i; } // initialize int[][] dp = new int[N + 1][V + 1]; for (int[] i : dp) { // should avoid overflow for dp[i][j - v[i]] + w[i] Arrays.fill(i, Integer.MAX_VALUE >> 1); } dp[0][0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= V; j++) { if (v[i] > j) { // value[i] > j dp[i + 1][j] = dp[i][j]; } else { // should avoid overflow for dp[i][j - v[i]] + w[i] dp[i + 1][j] = Math.min(dp[i][j], dp[i][j - v[i]] + w[i]); } } } // search for the largest i dp[N][i] <= W for (int i = V; i >= 0; i--) { // if (dp[N][i] <= W) return i; if (dp[N][i] <= W) return i; } return 0; } // repeated backpack public static int backpack3(int W, int[] w, int[] v) { int N = w.length; int[][] dp = new int[N + 1][W + 1]; for (int i = 0; i < N; i++) { for (int j = 0; j <= W; j++) { if (w[i] > j) { // backpack cannot hold w[i] dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = Math.max(dp[i][j], dp[i + 1][j - w[i]] + v[i]); } } } return dp[N][W]; } public static void main(String[] args) { int[] w1 = new int[]{2, 1, 3, 2}; int[] v1 = new int[]{3, 2, 4, 2}; int W1 = 5; boolean[] itemTake = new boolean[w1.length + 1]; System.out.println("Testcase for 01 backpack."); int bp1 = backpack(W1, w1, v1, itemTake); // bp1 should be 7 System.out.println("Maximum value: " + bp1); for (int i = 0; i < itemTake.length; i++) { if (itemTake[i]) { System.out.println("item " + i + ", weight " + w1[i] + ", value " + v1[i]); } } System.out.println("Testcase for 01 backpack with large W."); int bp2 = backpack2(W1, w1, v1); // bp2 should be 7 System.out.println("Maximum value: " + bp2); int[] w3 = new int[]{3, 4, 2}; int[] v3 = new int[]{4, 5, 3}; int W3 = 7; System.out.println("Testcase for repeated backpack."); int bp3 = backpack3(W3, w3, v3); // bp3 should be 10 System.out.println("Maximum value: " + bp3); } } ~~~ ### Reference - 《挑戰程序設計競賽》第二章 - Chapter 6.4 Knapsack *Algorithm - S. Dasgupta* - [0019算法筆記——【動態規劃】0-1背包問題 - liufeng_king的專欄](http://blog.csdn.net/liufeng_king/article/details/8683136) - [崔添翼 § 翼若垂天之云 ? 《背包問題九講》2.0 alpha1](http://cuitianyi.com/blog/%E3%80%8A%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E4%B9%9D%E8%AE%B2%E3%80%8B2-0-alpha1/) - [Knapsack.java](http://introcs.cs.princeton.edu/java/96optimization/Knapsack.java.html)