在lintcode上第一次遇到背包问题。挺有意思的。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。这个问题可以用穷举的方法解决，但效率有点低。
可以用以下解法提高解题效率。
定义一个二维数组dp
//符号说明 dp[i][j] //表示最大容量为j时，前i项物品（有选择性）装进背包中的最大价值 w[i] //第i个物品的价值
当i等于0的时候d[i][j] 均为0
当i>1时，可以通过以下推导式得到(j应当从大到小，避免从小到大出现覆盖的情况)
if (j > w[i]) max(dp[i-1][j] , dp[i-1][j-w[i]]+w[i])
这个推导式首先是判断j(背包容量)是否大于w[i] (该物品重量)
当容量足够大的时候才更新更优的重量，
这个更新最优的重量是从以下两种情况取最大值：
1.背包不增加该物品
2.背包增加该物品，此外背包剩下的空间，取之前计算过的该容量的最优值也就是dp[i-1][j-w[i]]
这个算法优势在于：
第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定
实际上该算法也可以压缩以下空间用一维数组存储，最后给出算法c++实现
class Solution {
public:
int weightCapacity(vector &weights, int maxCapacity) {
// Write your code here
sort(weights.begin(),weights.end());//排序
vector dp(maxCapacity+1);
for(int i = 0;i< weights.size();i++){
for(int j =maxCapacity;j>=weights[i];j--){
if(j>weights[i]){
dp[j] = max(dp[j-weights[i]]+weights[i],dp[j]);
}
}
}
return dp.back();
}
};
参考资料
