# Backpack II

## [Backpack II](https://www.lintcode.com/problem/backpack-ii/description) (0 - 1背包问题)

## 0-1 knapsack problem

### 单次选择 + 最大价值

### Question

Given `n` items with size `Ai` and value `Vi`, and a backpack with size m. What's the maximum value can you put into the backpack?

**Notice**

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 `9`.

**Challenge**

O(n x m) memory is acceptable, can you do it in O(m) memory?

**Tags**

LintCode Copyright Dynamic Programming Backpack

**Related Problems**

Medium Backpack VI 30 %\
Medium Backpack V 39 %\
Medium Backpack IV 36 %\
Hard Backpack III 50 %\
Medium Backpack 23 %

### Analysis

<https://github.com/tianyicui/pack/blob/master/V2.pdf>

最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。0 - 1

子问题定义状态：即 `F[i, v]` 表示前 i 件物品放入一个容量为 `v` 的背包可以获得 的最大价值

其状态转移方程便是： `F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci ] + Wi}`

**DP四要素**

* 状态 State
  * `f[i][j]` **表示前 i 个物品当中选一些物品组成容量为 j 的最大价值**
* 方程 Function
  * `f[i][j] = max(f[i-1][j], f[i-1][j-A[i-1]] + V[i-1])`;
* 初始化 Initialization
  * `f[0][0] = 0`;
* 答案 Answer
  * `f[n][s]`
* 时间复杂度 O(n\*s)

### Solution

2D DP

```java
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */

     public int backPackII_2(int m, int[] A, int[] V) {
        // maximum value of using first i items under total size j
        int[][] dp = new int[A.length + 1][m + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= A[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i-1][j - A[i - 1]] + V[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[A.length][m];
    }
}
```

1D DP space Optimized

用一维数组优化

```java
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */

    public int backPackII(int m, int[] A, int[] V) {
        // maximum value of using first i items under total size j
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j >= A[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
            }
        }
        return dp[m];
    }
}
```