# Backpack

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

## 0-1 knapsack problem

### 单次选择 + 最大体积

### Question

Given `n` items with size `Ai`, an integer `m` denotes the size of a backpack. How full you can fill this backpack?

**Notice**

You can not divide any item into small pieces.

**Example**

If we have 4 items with size \[2, 3, 5, 7], the backpack size is 11, we can select \[2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select \[2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

**Challenge**

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

**Tags**

LintCode Copyright Dynamic Programming Backpack

**Related Problems**

Medium Backpack VI 30 %\
Medium Backpack V 38 %\
Medium Backpack IV 36 %\
Hard Backpack III 50 %\
Medium Backpack II 37 %

### Analysis

背包问题序列I

**要点： 单次选择+最大体积**

常用是DP，但也可以用递归+记忆化搜索来做。

这个问题没有给每个物品的价值，也没有问最多能获得多少价值，而是问最多能装多满。

实际上在这里，如果我们把每个物品的大小当作每个物品的价值，就可以完美解决这个问题。

### Solution

#### **Preferred Solution**

**2D - DP**

**状态：**

`dp[i][j]` - 代表在前 `i` 件物品中选择若干件，这若干件物品的体积和不超过 `j` 的情况下，所能获得的最大容量

外层循环`A[i]`, 内层循环`j`

**状态转移：**

```java
if (j >= A[i - 1]) {
    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
} else {
    dp[i][j] = dp[i - 1][j];
}
```

2D DP

```java
    public int backPack(int m, int[] A) {
        int[][] dp = new int[A.length + 1][m + 1];
        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]] + A[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[A.length][m];
    }
```

Or Another 2D DP

```java
   public int backPackI(int m, int[] A) {
        int dp[][] = new int[A.length + 1][m + 1];
        for(int i = 1; i < A.length + 1; i++){
            for(int j = 0; j < m + 1; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= A[i - 1]){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - A[i-1]] + A[i-1]);
                }
            }
        }
        return dp[A.length][m];
    }
```

**1D - DP**

**State: 数组**`dp[i]`表示书包空间为`i`的时候能装的A物品最大容量

动规经典题目，用数组`dp[i]`表示书包空间为`i`的时候能装的A物品最大容量。

两次循环，**外部遍历数组A，内部反向遍历数组dp**，若`j`即背包容量大于等于物品体积`A[i]`，则取前`i - 1`次循环求得的最大容量`dp[j]`，和背包体积为`j - A[i]`时的最大容量`dp[j - A[i]]`与第`i`个物品体积`A[i]`之和即`dp[j - A[i]] + A[i]`的较大值，作为本次循环后的最大容量`dp[i]`。

注意`dp[]`的空间要给`m+1`，因为我们要求的是第`m+1`个值`dp[m]`，否则会抛出OutOfBoundException。

**一维数组优化：**

在第 `i` 层循环初 `dp[j]` 存的相当于 `dp[i - 1][j]` 的值，因为在更新`dp[j]`时用到了 `dp[j - A[i]]`, 由于**内层循环倒序**，所以`dp[j - A[i]]` 未被更新，因此代表了`dp[i-1][j - A[i]]`。

1D space optimized:

```java
public class Solution {
    public int backPack(int m, int[] A) {
        int[] dp = new int[m+1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
                }
            }
        }
        return dp[m];
    }
}
```

1D DP

j = m, m-1, ..., A\[i]

```java
    public int backPack(int m, int[] A) {
        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]] + A[i]);
            }
        }
        return dp[m];
    }
```

#### Another DP Approach (NOT Preferred)

2D with O(n \* *m) time and O(n \** m) space.

**动态规划4要素**

* **State:**
  * `f[i][S]` **“前i”个物品，取出一些*****能否*****组成和为S**
* **Function:**
  * `f[i][S] = f[i-1][S - a[i]]` or `f[i-1][S]`
* **Initialize:**
  * `f[i][0] = true`; `f[0][1..target] = false`
* **Answer:**
  * 检查所有的`f[n][j]`

O(n \* S) ， 滚动数组优化

注意这里A\[i - 1]的数组下标，因为新建的是i = 1, ..., A.length

```java
public class Solution {
    /**
    * @param m: An integer m denotes the size of a backpack
    * @param A: Given n items with size A[i]
    * @return: The maximum size
    */
    public int backPack(int m, int[] A) {
        boolean[][] dp = new boolean[A.length + 1][m + 1];

        dp[0][0] = true;

        for (int i = 1; i <= A.length; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] || (j - A[i - 1] >= 0 && dp[i - 1][j - A[i - 1]]);
            }
        }

        for (int j = m; j >= 0; j--) {
            if (dp[A.length][j]) {
                return j;
            }
        }

        return 0;
    }
}
```

1D version with O(n \* m) time and O(m) memory.

```java
public class Solution {
    /**
    * @param m: An integer m denotes the size of a backpack
    * @param A: Given n items with size A[i]
    * @return: The maximum size
    */
    public int backPack(int m, int[] A) {
        if (A.length == 0) return 0;

        int n = A.length;
        boolean[] dp = new boolean[m + 1];
        Arrays.fill(dp, false);
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 0; j--) {
                if (j - A[i - 1] >= 0 && dp[j - A[i - 1]]) {
                    dp[j] = dp[j - A[i - 1]];
                }
            }
        }


        for (int i = m; i >= 0;i--) {
            if (dp[i]) return i;
        }


        return 0;
    }
}
```

#### Memoization + Search

<https://www.jiuzhang.com/solution/backpack/#tag-other>

```java
    int max =  Integer.MAX_VALUE;
    public int backPack(int m, int[] A) {

        Arrays.sort(A);
        boolean[] visited = new boolean[m + 1];
        int[] memo = new int[m + 1];
        dfs( m , A , 0 ,visited , memo );
        return m - max ;

    }
    private int dfs( int target , int[] A , int startIndex , boolean[] visited , int[] memo){
        if(visited[target]){
            return memo[target];
        }
        int res = target;
        for(int i = startIndex ; i < A.length ; i++){
            if(target - A[i] >=  0){
                res = dfs( target - A[i] , A , i + 1 ,visited ,memo);
            }
            else{
                break;
            }
        }
        visited[target] = true;
        memo[target] = res;
        max = Math.min(max ,res);
        return res; 
    }
```

### Reference

* [Backpack - neverlandly - 博客园](http://www.cnblogs.com/EdwardLiu/p/4269149.html)


---

# 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.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.