# Backpack II

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

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

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`;

• `f[n][s]`

• 时间复杂度 O(n*s)

### Solution

2D DP

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

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

Last updated