# Backpack

## Question

### Problem Statement

Given n items with size $A_i$, 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.

## 题解1

### 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 == null || A.length == 0) return 0;

final int M = m;
final int N = A.length;
int[][] bp = new int[N + 1][M + 1];

for (int i = 0; i < N; i++) {
for (int j = 0; j <= M; j++) {
if (A[i] > j) {
bp[i + 1][j] = bp[i][j];
} else {
bp[i + 1][j] = Math.max(bp[i][j], bp[i][j - A[i]] + A[i]);
}
}
}

return bp[N][M];
}
}


## 题解2

1. 状态: result[i][S] 表示前i个物品，取出一些物品能否组成体积和为S的背包
2. 状态转移方程: $f[i][S] = f[i-1][S-A[i]] ~or~ f[i-1][S]$ (A[i]为第i个物品的大小)
• 欲从前i个物品中取出一些组成体积和为S的背包，可从两个状态转换得到。
1. $f[i-1][S-A[i]]$: 放入第i个物品，前 $i-1$ 个物品能否取出一些体积和为 $S-A[i]$ 的背包。
2. $f[i-1][S]$: 不放入第i个物品，前 $i-1$ 个物品能否取出一些组成体积和为S的背包。
3. 状态初始化: $f[1 \cdots n][0]=true; ~f[0][1 \cdots m]=false$. 前1~n个物品组成体积和为0的背包始终为真，其他情况为假。
4. 返回结果: 寻找使 $f[n][S]$ 值为true的最大S ($1 \leq S \leq m$)

### C++ - 2D vector

class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> A) {
if (A.empty() || m < 1) {
return 0;
}

const int N = A.size() + 1;
const int M = m + 1;
vector<vector<bool> > result;
result.resize(N);
for (vector<int>::size_type i = 0; i != N; ++i) {
result[i].resize(M);
std::fill(result[i].begin(), result[i].end(), false);
}

result[0][0] = true;
for (int i = 1; i != N; ++i) {
for (int j = 0; j != M; ++j) {
if (j < A[i - 1]) {
result[i][j] = result[i - 1][j];
} else {
result[i][j] = result[i - 1][j] || result[i - 1][j - A[i - 1]];
}
}
}

// return the largest i if true
for (int i = M; i > 0; --i) {
if (result[N - 1][i - 1]) {
return (i - 1);
}
}
return 0;
}
};


### 源码分析

1. 异常处理
2. 初始化结果矩阵，注意这里需要使用resize而不是reserve，否则可能会出现段错误
3. 实现状态转移逻辑，一定要分j < A[i - 1]与否来讨论
4. 返回结果，只需要比较result[N - 1][i - 1]的结果，返回true的最大值

        for (int i = 1; i != N; ++i) {
for (int j = 0; j != M; ++j) {
result[i][j] = result[i - 1][j];
if (j >= A[i - 1] && result[i - 1][j - A[i - 1]]) {
result[i][j] = true;
}
}
}


### C++ - 1D vector

class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> A) {
if (A.empty() || m < 1) {
return 0;
}

const int N = A.size();
vector<bool> result;
result.resize(m + 1);
std::fill(result.begin(), result.end(), false);

result[0] = true;
for (int i = 0; i != N; ++i) {
for (int j = m; j >= 0; --j) {
if (j >= A[i] && result[j - A[i]]) {
result[j] = true;
}
}
}

// return the largest i if true
for (int i = m; i > 0; --i) {
if (result[i]) {
return i;
}
}
return 0;
}
};