原题
Description
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.
解题
背包问题，经典的动态规划问题。
首先理解一个二维数组dp[i][j]，它代表只考虑物品列表A中的前i个物品时，空间为j的背包被占用空间的最大值。
此时我们可以得知两个信息
- 对于任意
i，dp[i][0] = 0，即背包空间为0，无论有多少个物品都不能放入背包，因此背包被占用的空间是0，最大值也是0。 - 对于任意
j，dp[0][j] = 0，即不考虑放入任何物品时，无论背包多大，背包被占用的空间都是0，最大值当然也就是0。 -
dp[A.size()][m]为答案，即考虑A中的所有物品，背包容量为m时，背包被占用空间的最大值，不是答案是啥。
例子
为了便于理解，这里再举一个例子物品列表A {2, 3, 4}
dp[1][6]和dp[2][6]
dp[1][6]表示：只考虑前1个物品也就是空间占用为2的物品，背包空间为6。这时候有两个选择，放这个物品和不放。如果放，则总空间占用是2，如果不放则空间占用变为0，明显前者是要更好的。所以dp[1][6] = 2
dp[2][6]表示：只考虑前两个物品，即空间占用为2、3的两个物品，背包空间为6。现在我们面临两个选择，物品3放还是不放：
- 如果不放，那么背包还是6。问题转化为dp[1][6]，也就是只考虑第一个物品2，背包空间为6。很明显
dp[1][6] = 2，所以不放物品3的情况下，空间占用为2。 - 如果放，那么背包空间变为3。问题转化为dp[1][3]，也就是只考虑物品2，背包空间为4.
dp[1][4] = 2，所以放物品3的情况下，空间占用是dp[1][4] + 3 = 5
取上述占用最多的，所以dp[2][6] = 5。
从上面的例子可以看出来，其实dp[2][6] = max( dp[1][6], dp[1][6 - 3] + 3 ) = 5
状态转移方程
考虑以下情况：
背包空间为m，物品列表A中共有n个商品，其中A[i]表示每个商品的空间。求背包最多能被填多满。
根据上面的表述我们得知dp[n][m]即为需要的答案，同时根据上面的例子我们可以得知
dp[n][m] = dp[n - 1][m], dp[n - 1][m - A[n]] + A[n]
解释：这里和上面的例子一样，也是最后一个物品n放不放的问题，不放则转化为dp[n-1][m]，放则转化为dp[n-1][m-A[n]]+A[n]。取其中的较大值即可。
那么我们可以总结出一个较为通用的计算公式，即状态转移方程：
只考虑前i个商品，背包空间为j，则
dp[i][j] = dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]
for i=0..n
for j=0...m
dp[i][j] = dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]
优化空间复杂度
可以发现这时候选O(mn)的空间复杂度。因为我们由一个主循环i=0..n，嵌套一个循环j=0...m来计算每个dp[i][j]的值。
然而如果我们的第二重以j=m...0的方式反向循环，状态转移方程可以写成
dp[j] = max( dp[j], dp[j - A[i]] + A[i] )
for i=0..n
for j=0...m
dp[j] = max( dp[j], dp[j - A[i]] + A[i] )
此时空间复杂度为O(m)
代码
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) {
// write your code here
vector<int> dp(m + 1);
for (int i = 0; i < A.size(); i++) {
for (int j = m; j > 0; j--) {
if (j >= A[i]) {
dp[j] = max(dp[j], dp[j - A[i]] + A[i]);
}
}
}
return dp.back();
}
};
