Backpack II
最后更新于：2022-04-02 01:12:45
# Backpack II
### Source
- lintcode: [(125) Backpack II](http://www.lintcode.com/en/problem/backpack-ii/)
### Problem
Given *n* items with size AiAiAi and value Vi, and a backpack with size *m*.What's the maximum value can you put into the backpack?
#### Example
Given 4 items with size `[2, 3, 5, 7]` and value `[1, 5, 2, 4]`, and abackpack with size `10`. The maximum value is `9`.
#### Note
You cannot divide item into small pieces and the total size of items youchoose should smaller or equal to m.
#### Challenge
O(n x m) memory is acceptable, can you do it in O(m) memory?
### 题解
首先定义状态 K(i,w)K(i,w)K(i,w) 为前 iii 个物品放入size为 www 的背包中所获得的最大价值，则相应的状态转移方程为：K(i,w)=max{K(i−1,w),K(i−1,w−wi)+vi}K(i,w) = \max \{K(i-1, w), K(i-1, w - w_i) + v_i\}K(i,w)=max{K(i−1,w),K(i−1,w−wi)+vi}
详细分析过程见 [Knapsack](http://algorithm.yuanbin.me/zh-cn/basics_algorithm/knapsack.html)
### C++ - 2D vector for result
~~~
class Solution {
public:
/**
* @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
*/
int backPackII(int m, vector A, vector V) {
if (A.empty() || V.empty() || m < 1) {
return 0;
}
const int N = A.size() + 1;
const int M = m + 1;
vector > result;
result.resize(N);
for (vector::size_type i = 0; i != N; ++i) {
result[i].resize(M);
std::fill(result[i].begin(), result[i].end(), 0);
}
for (vector::size_type 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 {
int temp = result[i - 1][j - A[i - 1]] + V[i - 1];
result[i][j] = max(temp, result[i - 1][j]);
}
}
}
return result[N - 1][M - 1];
}
};
~~~
### Java
~~~
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(int m, int[] A, int V[]) {
if (A == null || V == null || A.length == 0 || V.length == 0) return 0;
final int N = A.length;
final int M = m;
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]] + V[i]);
}
}
}
return bp[N][M];
}
}
~~~
### 源码分析
1. 使用二维矩阵保存结果result
1. 返回result矩阵的右下角元素——背包size限制为m时的最大价值
按照第一题backpack的思路，这里可以使用一维数组进行空间复杂度优化。优化方法为逆序求`result[j]`，优化后的代码如下：
### C++ 1D vector for result
~~~
class Solution {
public:
/**
* @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
*/
int backPackII(int m, vector A, vector V) {
if (A.empty() || V.empty() || m < 1) {
return 0;
}
const int M = m + 1;
vector result;
result.resize(M);
std::fill(result.begin(), result.end(), 0);
for (vector::size_type i = 0; i != A.size(); ++i) {
for (int j = m; j >= 0; --j) {
if (j < A[i]) {
// result[j] = result[j];
} else {
int temp = result[j - A[i]] + V[i];
result[j] = max(temp, result[j]);
}
}
}
return result[M - 1];
}
};
~~~
### Reference
- [Lintcode: Backpack II - neverlandly - 博客园](http://www.cnblogs.com/EdwardLiu/p/4272300.html)
- [九章算法 | 背包问题](http://www.jiuzhang.com/problem/58/)
';