0-1背包问题描述：一个正在抢劫商店的小偷发现了n个商品，第i个商品价值 vi 美元，重 wi 磅，vi 和 wi 都是整数。这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳 S 磅重的商品，S 是一个整数，那么他应该如何拿才能使得背包中的商品价值之和最大。
0-1背包问题的特点在于这类问题只能做出二元选择，比如上面描述的问题中每个商品不可拆分，小偷要么把它拿走，要么把它留下；不能拿走商品的一部分。所以有可能最后结果小偷的背包还有多余的空间，但却不能再多放商店的商品了。这也是使用动态规划求解方法的原因。
代码：
#include <iostream>
#include <vector>
#include <minmax.h>
#define MAXSIZE 0xffff
class DP {
public:
int KnapsackProblem(std::vector<int> & v, std::vector<int> & w, int S)
{
std::vector<int> dp(MAXSIZE, 0);
for (int i = 0; i < v.size(); i++)
for (int j = S; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
return dp[S];
}
};
int main()
{
std::vector<int> v{ 160,100,120,220 };
std::vector<int> w{ 30,10,20,20 };
int S = 50;
std::cout << DP().KnapsackProblem(v, w, S) << std::endl;
getchar();
return 0;
}
算法参考：
1.http://blog.csdn.net/hearthougan/article/details/53869671
2.http://www.cnblogs.com/sench/p/8011948.html