# 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经典

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

和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示意图：**\
![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F660196a099f0ae570a32e4f46bcd0e3792c7286e.jpeg?generation=1588144786176791\&alt=media)

**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 可以省略:&#x20;
  * `(i - 1)`th row 不过是需要用到之前算出的旧value: 每一轮, j = \[0 \~ m], 那么`dp[j]`本身就有记录旧值的功能.
  * 变成1个一维数组
* **降维优化的重点**: **看双行的左右计算方向**
* Time: `O(mn)`.&#x20;
* 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)` 的优秀算法。

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

> `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](https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-iii)<https://www.jiuzhang.com/tutorial/backpack/94>
* [Backpack III by zhengyang2015](https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html)