92-背包问题
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
注意事项
你不可以将物品进行切割。
样例
如果有4个物品[2, 3, 5, 7]
如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。
如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。
函数需要返回最多能装满的空间大小。挑战
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.标签
动态规划 背包问题 LintCode 版权所有
方法一（空间复杂度O(n x m) ）
使用二维数组 dp[i][j] 记录前 i 个数，在背包大小为 j 的条件下，最多可以装满的空间
在仅有一个物品元素时，最多可装满的空间就是此物品大小（前提是背包可以装下此物品）
有多个元素时，要装入一个新元素，则最多可以装满的空间就是装入此元素前，背包大小为当前背包大小-此元素大小的大小+此元素的大小（装入新元素），或不变（未能装下此元素）
也可以解释为：
不放第i个物品：dp[i-1][j]
放第i个物品：那么问题就转化为“前i-1件物品放入剩下的容量为j-A[i]的背包中”，此时能获得的最大体积就是dp[i-1][j-A[i]]再加上通过放入第i件物品获得的体积A[i]
转自http://www.cnblogs.com/theskulls/p/5487061.html
具体过程如下图所示：
状态转移方程为：dp[i][j] = max(dp[i - 1][j - A[i]] + A[i], dp[i - 1][j])
code
class Solution {
public:
/**
* http://www.lintcode.com/zh-cn/problem/backpack/-92-背包问题
* @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
int size = A.size(), i = 0, j = 0;
if(size <= 0) {
return 0;
}
sort(A.begin(), A.end());
vector< vector<int> > dp(size, vector<int>(m+1, 0) );
for(i=0; i<size; i++) {
for(j=1; j<=m; j++) {
if(i==0 && j>=A[i]) {
dp[i][j] = A[i];
}
else if(i>0 && j>=A[i]){
dp[i][j] = (dp[i-1][j-A[i]] + A[i] > dp[i-1][j]) ? dp[i-1][j-A[i]] + A[i] : dp[i-1][j];
}
else if(i>0 && j<A[i]){
dp[i][j] = dp[i-1][j];
}
}
}
return dp[size-1][m];
}
};
方法二（空间复杂度 O(m) ）
优化方法一的状态方程，使用一维数组 dp[i] 记录所有物品在背包大小为 j 的条件下，最多可以装满的空间
在方法一中，二维数组的每一行仅仅与其上一行相关，所以可以将二维数组压缩成一维数组，可以相成用二维数组的下一行将上一行覆盖
因为新的结果要与其在二维素组中左上位置的元素比较（即一维数组中左边的元素比较），所以从后向前遍历一维数组，并写入新元素
状态转移方程为：dp[j] = max(dp[j], dp[j - A[i]] + A[i])
code
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
int size = A.size(), i = 0, j = 0;
if(size <= 0) {
return 0;
}
int *dp = new int[m+1];
for(i=0; i<m+1; i++) {
dp[i] = 0;
}
for(i=0; i<size; i++) {
for(j=m; j>=1; j--) {
if(j >= A[i]) {
dp[j] = (dp[j]>dp[j-A[i]] + A[i])?dp[j]:dp[j-A[i]] + A[i];
}
}
}
return dp[m];
}
};