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


---

# Agent Instructions: 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_ii.md?ask=<question>
```

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.