> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-iii.md). # Backpack III ## unbounded knapsack problem (UKP) ## 重复选择 + 最大价值 **Hard** ### Description Given*n\_kind of items with size Aiand value Vi(*`each item has an infinite number available`*) and a backpack with size\_m*. What's the maximum value can you put into the backpack? You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m. ### Example Given 4 items with size`[2, 3, 5, 7]`and value`[1, 5, 2, 4]`, and a backpack with size`10`. The maximum value is`15`. ## Analysis 完全背包问题，DP经典 和II不同的是，这道题物品可以重复选择，所以内层遍历j的时候从小到大遍历，这样物品可以重复选取。比如一开始在`j`的时候取了`i`，然后随着j的增大，在`j'`的时候又取了`i`，而恰好`j = j' - A[i]`，在这种情况下`i`就被重复选取。如果从大往小遍历则所有物品只能取一次，所以II中是从大往小遍历。 **因此可以重复取元素则背包容量从小到大遍历，反之从大到小遍历。** #### 转化为多重背包问题 将其视为多重背包变形，每种物品取的上限是`m / A[i]`。 * 可以无限使用物品, 就失去了last i, last unique item的意义: 因为可以重复使用. 所以可以转换一个角度: * i. 用 `i` **种** 物品, 拼出`j`大小, 并且满足题目条件(max value). 这里因为item `i`可以无限次使用, 所以考虑使用了多少次`K`. * ii. `k`虽然可以无限, 但是也被 `k * A[i]`所限制: **最大不能超过背包大小**. * `dp[i][j]`: **前**`i`**种物品, fill weight** `j` **的背包, 最大价值是多少.** * `dp[i][j] = max {dp[i - 1][j - k*A[i-1]] + k*V[i-1]}, k >= 0, k <= j / A[i-1]` * Time: `O(nmk)` * 如果k = 0 或者 1, 其实就是 *Backpack II*: 0-1背包，拿或者不拿 **2D - DP示意图：**\ ![](/files/-M63nX-vrvNIOh1StHC7) **2D - DP 代码实现：** ```java /* Thoughts: dp[i][w]: first i types of items to fill weight w, find the max value. 1st loop: which type of item to pick from A 2nd loop: weight from 0 ~ m 3rd loop: # times when A[i] is used. Goal: dp[n][m] Condition1: didn't pick A[i - 1], dp[i][j] = dp[i - 1][j]; Condition2: pickced A[i - 1], dp[i][j] = dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]; O(nmk) */ public class Solution { public int backPackIII(int[] A, int[] V, int m) { if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; dp[0][0] = 0; // 0 items to fill 0 weight, value = 0 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j]; for (int k = 1; k * A[i - 1] <= j; k++) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]); } } } return dp[n][m]; } } ``` Minor Modified ```java public class Solution { public int backPackIII(int[] A, int[] V, int m) { if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; dp[0][0] = 0; // 0 items to fill 0 weight, value = 0 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = 0; k * A[i - 1] <= j; k++) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]); } } } return dp[n][m]; } } ``` #### 时间复杂度优化 * 优化时间复杂度, 通过画图（见以上示意图）发现: * 所计算的 (`dp[i - 1][j - k*A[i - 1]] + k * V[i - 1]`) ，其实跟同一行的 `dp[i][j-A[i-1]]` 那个格子相比, 就多出了 `V[i-1]` * 所以没必要每次都 loop over `k` times * 简化: `dp[i][j]` 其中一个可能就是: `dp[i][j - A[i - 1]] + V[i - 1]` * Time: `O(mn)` * Space: `O(mn)` ```java /** Optimization1: - 优化时间复杂度, 画图发现: - 所计算的 (dp[i - 1][j - k*A[i - 1]] + k * V[i - 1]) - 其实跟同一行的 dp[i][j-A[i-1]] 那个格子, 就多出了 V[i-1] - 所以没必要每次都 loop over k times - 简化: dp[i][j] 其中一个可能就是: dp[i][j - A[i - 1]] + V[i - 1] */ public class Solution { public int backPackIII(int[] A, int[] V, int m) { if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) { return 0; } int n = A.length; int[][] dp = new int[n + 1][m + 1]; dp[0][0] = 0; // 0 items to fill 0 weight, value = 0 for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i][j] = dp[i - 1][j]; if (j >= A[i - 1]) { dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]); } } } return dp[n][m]; } } ``` #### 空间复杂度优化 **空间优化到1维数组** * 根据上一个优化的情况, 画出 2 rows 网格 * 发现 `dp[i][j]` 取决于: 1. `dp[i - 1][j]`, 2. `dp[i][j - A[i - 1]]` * 其中: `dp[i - 1][j]` 是上一轮 `(i-1)` 的结算结果, 一定是已经算好, ready to be used 的 * 然而, 当我们 `i++`, `j++` 之后, 在之前 `row = i - 1`, `col < j` 的格子, 全部不需要. * **降维简化**: 只需要留着 weigth，也就是`j`这个 dimension, 而 `i` 这个dimension 可以省略: * `(i - 1)`th row 不过是需要用到之前算出的旧value: 每一轮, j = \[0 \~ m], 那么`dp[j]`本身就有记录旧值的功能. * 变成1个一维数组 * **降维优化的重点**: **看双行的左右计算方向** * Time: `O(mn)`. * Space: `O(m)` ```java /** Optimization2: - 根据上一个优化的情况, 画出 2 rows 网格 - 发现 dp[i][j] 取决于: 1. dp[i - 1][j], 2. dp[i][j - A[i - 1]] - 其中: dp[i - 1][j] 是上一轮 (i-1) 的结算结果, 一定是已经算好, ready to be used 的 - 然而, 当我们 i++,j++ 之后, 在之前 row = i - 1, col < j的格子, 全部不需要. - 降维简化: 只需要留着 weigth 这个 dimension, 而i这个dimension 可以省略: - (i - 1) row 不过是需要用到之前算出的旧value: 每一轮, j = [0 ~ m], 那么dp[j]本身就有记录旧值的功能. */ public class Solution { public int backPackIII(int[] A, int[] V, int m) { if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) { return 0; } int n = A.length; int[] dp = new int[m + 1]; // DP on weight dp[0] = 0; // 0 items to fill 0 weight, value = 0 for (int i = 1; i <= n; i++) { for (int j = A[i - 1]; j <= m && j >= A[i - 1]; j++) { dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]); } } return dp[m]; } } ``` **关于最优化算法的细节：** 时间复杂度为 `O(mn)`，空间复杂度为 `O(m)` 九章： > 优化的方法十分简单，我们只需要将 `j` 的循环由**逆向**转变为**正向**即可。 想一想，为什么？\ > 由于同一种物品的个数无限，所以我们可以在任意容量 `j` 的背包尝试装入当前物品，`j` 从**小向大枚举**可以保证所有包含第 `i` 种物品，体积不超过 `j - A[i]` 的状态被枚举到。 从而得到时间复杂度为 `O(mn)`，空间复杂度为 `O(m)` 的优秀算法。 > `j`从大到小取，可以保证`dp[j]`里面的值是每个item只取了一个的时候的最优值。所以01背包和多重背包的k循环只能从大到小取，而完全背包的k循环从大到小和从小到大都可以。这是01背包/多重背包和完全背包的一个重要区别！ **正序和逆序的区别就是，对于正序，**`j`**以前的状态是当前行的状态；对于逆序，**`j`**以前的状态是上一个行的状态。** ## Reference * [**awangdev @ GitHub: LintCode - Backpack III**](https://github.com/awangdev/LintCode/blob/master/Java/Backpack%20III.java) * [LintCode 440: Backpack III (完全背包问题，DP经典)](https://blog.csdn.net/roufoo/article/details/83117144) * [jiuzhang tutorial](/lintcode/knapsack_problems/backpack-iii.md) * [Backpack III by zhengyang2015](https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html) --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-iii.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.