# Backpack I&II

## – different sizes same price, ask maximum solution with fixed bag size

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

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.

Note

You can not divide any item into small pieces.

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.

### Solution 1: DP – O(nm) time and O(nm) memory

state: f[i][j] = “前i”个数，取出一些组成和为<=j的最大值

function: f[i][j] = f[i-1][j – a[i]] + a[i] //取a[i]的情况

o f[i-1][j] //不取a[i]的情况

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i][j] = backPack[i - 1][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i][j] = Math.max(backPack[i][j], backPack[i - 1][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i][j] > max) {
max = backPack[i][j];
}
}
}
return max;
}```

### Solution 2. O(mn) time O(n) space, 利用行数取模优化空间 rolling array

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
int[][] backPack = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
backPack[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
backPack[0][j] = 0;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
//doesn't contain A[i]
backPack[i % 2][j] = backPack[(i - 1) % 2][j];
//contains A[i]
if (j >= A[i - 1]) {
backPack[i % 2][j] = Math.max(backPack[i % 2][j], backPack[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
}
if (backPack[i % 2][j] > max) {
max = backPack[i % 2][j];
}
}
}
return max;
}```

### Solution 3: dp

f[i][j] = 前i个item能不能正好组成j

f[i][j] = f[i-1][j-a[i]] //取a[i]

f[i-1][j] //不取a[i]

return max j which f[i][j] == true

```public int backPack(int m, int[] A) {
if (m <= 0 || A == null || A.length == 0) {
return 0;
}
boolean[][] backPack = new boolean[A.length + 1][m + 1];
backPack[0][0] = true;
for (int i = 1; i <= A.length; i++) {
backPack[i][0] = true;
}
for (int j = 1; j <= m; j++) {
backPack[0][j] = false;
}
int max = 0;
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
backPack[i][j] = backPack[i - 1][j];
if (j >= A[i - 1]) {
backPack[i][j] |= backPack[i - 1][j - A[i - 1]];
}
if (backPack[i][j]) {
max = j;
}
}
}
return max;
}```

## – different size and price, ask for maximum value with fixed bag size

### Solution 1. O(m*n) time, O(m*n) space

f[i][j]:maximum value with first i items in A with a m sized bag

f[i][j] = f[i-1][j – a[i]] + v[i] //取a[i]的情况

= f[i-1][j] //不取a[i]的情况

```public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[A.length + 1][m + 1];
for (int i = 0; i <= A.length; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i][j] = maxValue[i - 1][j];
if (j >= A[i - 1]) {
maxValue[i][j] = Math.max(maxValue[i][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length][m];
}```

### Solution 2: O(m*n) time, O(m) space

```public int backPackII(int m, int[] A, int V[]) {
if (A == null || V == null || m <= 0) {
return 0;
}
int[][] maxValue = new int[2][m + 1];
for (int i = 0; i < 2; i++) {
maxValue[i][0] = 0;
}
for (int j = 0; j <= m; j++) {
maxValue[0][j] = 0;
}
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= m; j++) {
maxValue[i % 2][j] = maxValue[(i - 1) % 2][j];
if (j >= A[i - 1]) {
maxValue[i % 2][j] = Math.max(maxValue[i % 2][j], maxValue[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[A.length % 2][m];
}```
Share