# Backpack III

## 重复选择 + 最大价值

Hard

### Description

Givenn_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

https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html

#### 转化为多重背包问题

• 可以无限使用物品, 就失去了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 代码实现：

``````/*
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

``````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)`

``````/**
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];
}
}``````

#### 空间复杂度优化

• 根据上一个优化的情况, 画出 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)`

``````/**
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];
}
}``````

https://blog.csdn.net/roufoo/article/details/83117144

`j`从大到小取，可以保证`dp[j]`里面的值是每个item只取了一个的时候的最优值。所以01背包和多重背包的k循环只能从大到小取，而完全背包的k循环从大到小和从小到大都可以。这是01背包/多重背包和完全背包的一个重要区别！

Last updated