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