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


powered by