Backpack · 數據結構與算法/leetcode/lintcode題解

# Backpack ### Source - lintcode: [(92) Backpack](http://www.lintcode.com/en/problem/backpack/) ### Problem Given *n* items with size AiA_iAi, an integer *m* denotes the size of a backpack.How full you can fill this backpack? #### Example If we have `4` items with size `[2, 3, 5, 7]`, the backpack size is 11, we canselect `[2, 3, 5]`, so that the max size we can fill this backpack is `10`. Ifthe backpack size is `12`. we can select `[2, 3, 7]` so that we can fulfillthe backpack. You function should return the max size we can fill in the given backpack. #### Note You can not divide any item into small pieces. #### Challenge O(n x m) time and O(m) memory. O(n x m) memory is also acceptable if you do not know how to optimize memory. ### 題解1 本題是典型的01背包問題，每種類型的物品最多只能選擇一件。參考前文 [Knapsack](http://algorithm.yuanbin.me/zh-cn/basics_algorithm/knapsack.html) 中總結的解法，這個題中可以將背包的 size 理解為傳統背包中的重量；題目問的是能達到的最大 size, 故可將每個背包的 size 類比為傳統背包中的價值。考慮到數組索引從0開始，故定義狀態`bp[i + 1][j]`為前 `i` 個物品中選出重量不超過`j`時總價值的最大值。狀態轉移方程則為分`A[i] > j` 與否兩種情況考慮。初始化均為0，相當于沒有放任何物品。 ### Java ~~~ public class Solution { /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ public int backPack(int m, int[] A) { if (A == null || A.length == 0) return 0; final int M = m; final int N = A.length; int[][] bp = new int[N + 1][M + 1]; for (int i = 0; i < N; i++) { for (int j = 0; j <= M; j++) { if (A[i] > j) { bp[i + 1][j] = bp[i][j]; } else { bp[i + 1][j] = Math.max(bp[i][j], bp[i][j - A[i]] + A[i]); } } } return bp[N][M]; } } ~~~ ### 源碼分析注意索引及初始化的值，尤其是 N 和 M 的區別，內循環處可等于 M。 ### 復雜度分析兩重 for 循環，時間復雜度為 O(m×n)O(m \times n)O(m×n), 二維矩陣的空間復雜度為 O(m×n)O(m \times n)O(m×n), 一維矩陣的空間復雜度為 O(m)O(m)O(m). ### 題解2 接下來看看 [九章算法](http://www.jiuzhang.com/solutions/backpack/) 的題解，**這種解法感覺不是很直觀，推薦使用題解1的解法。** 1. 狀態: result[i][S] 表示前i個物品，取出一些物品能否組成體積和為S的背包 1. 狀態轉移方程: f[i][S]=f[i?1][S?A[i]]?or?f[i?1][S]f[i][S] = f[i-1][S-A[i]] ~or~ f[i-1][S]f[i][S]=f[i?1][S?A[i]]?or?f[i?1][S] (A[i]為第i個物品的大小) - 欲從前i個物品中取出一些組成體積和為S的背包，可從兩個狀態轉換得到。 1. f[i?1][S?A[i]]f[i-1][S-A[i]]f[i?1][S?A[i]]: **放入第i個物品**，前 i?1i-1i?1 個物品能否取出一些體積和為 S?A[i]S-A[i]S?A[i] 的背包。 1. f[i?1][S]f[i-1][S]f[i?1][S]: **不放入第i個物品**，前 i?1i-1i?1 個物品能否取出一些組成體積和為S的背包。 1. 狀態初始化: f[1?n][0]=true;?f[0][1?m]=falsef[1 \cdots n][0]=true; ~f[0][1 \cdots m]=falsef[1?n][0]=true;?f[0][1?m]=false. 前1~n個物品組成體積和為0的背包始終為真，其他情況為假。 1. 返回結果: 尋找使 f[n][S]f[n][S]f[n][S] 值為true的最大S (1≤S≤m1 \leq S \leq m1≤S≤m) ### C++ - 2D vector ~~~ class Solution { public: /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ int backPack(int m, vector<int> A) { if (A.empty() || m < 1) { return 0; } const int N = A.size() + 1; const int M = m + 1; vector<vector<bool> > result; result.resize(N); for (vector<int>::size_type i = 0; i != N; ++i) { result[i].resize(M); std::fill(result[i].begin(), result[i].end(), false); } result[0][0] = true; for (int i = 1; i != N; ++i) { for (int j = 0; j != M; ++j) { if (j < A[i - 1]) { result[i][j] = result[i - 1][j]; } else { result[i][j] = result[i - 1][j] || result[i - 1][j - A[i - 1]]; } } } // return the largest i if true for (int i = M; i > 0; --i) { if (result[N - 1][i - 1]) { return (i - 1); } } return 0; } }; ~~~ ### 源碼分析 1. 異常處理 1. 初始化結果矩陣，注意這里需要使用`resize`而不是`reserve`，否則可能會出現段錯誤 1. 實現狀態轉移邏輯，一定要分`j < A[i - 1]`與否來討論 1. 返回結果，只需要比較`result[N - 1][i - 1]`的結果，返回true的最大值狀態轉移邏輯中代碼可以進一步簡化，即： ~~~ for (int i = 1; i != N; ++i) { for (int j = 0; j != M; ++j) { result[i][j] = result[i - 1][j]; if (j >= A[i - 1] && result[i - 1][j - A[i - 1]]) { result[i][j] = true; } } } ~~~ 考慮背包問題的核心——狀態轉移方程，如何優化此轉移方程？原始方案中用到了二維矩陣來保存result，注意到result的第i行僅依賴于第i-1行的結果，那么能否用一維數組來代替這種隱含的關系呢？我們**在內循環j處遞減即可**。如此即可避免`result[i][S]`的值由本輪`result[i][S-A[i]]`遞推得到。 ### C++ - 1D vector ~~~ class Solution { public: /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */ int backPack(int m, vector<int> A) { if (A.empty() || m < 1) { return 0; } const int N = A.size(); vector<bool> result; result.resize(m + 1); std::fill(result.begin(), result.end(), false); result[0] = true; for (int i = 0; i != N; ++i) { for (int j = m; j >= 0; --j) { if (j >= A[i] && result[j - A[i]]) { result[j] = true; } } } // return the largest i if true for (int i = m; i > 0; --i) { if (result[i]) { return i; } } return 0; } }; ~~~ ### 復雜度分析兩重 for 循環，時間復雜度均為 O(m×n)O(m \times n)O(m×n), 二維矩陣的空間復雜度為 O(m×n)O(m \times n)O(m×n), 一維矩陣的空間復雜度為 O(m)O(m)O(m). ### Reference - 《挑戰程序設計競賽》第二章 - [Lintcode: Backpack - neverlandly - 博客園](http://www.cnblogs.com/EdwardLiu/p/4269149.html) - [九章算法 | 背包問題](http://www.jiuzhang.com/problem/58/) - [崔添翼 § 翼若垂天之云 ? 《背包問題九講》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/)