# 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

Related Problems

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

## Solution

#### Preferred Solution

##### 2D - DP

`dp[i][j]` - 代表在前 `i` 件物品中选择若干件，这若干件物品的体积和不超过 `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];
}
``````

2D DP

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

``````   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物品最大容量

1D space optimized:

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

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

• 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`
• 检查所有的`f[n][j]`

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

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

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

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

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