摘抄：http://www.cnblogs.com/Anker/archive/2013/05/04/3059070.html
1. 0-1背包问题描述
有一个窃贼在偷窃一家商店时发现有n件物品，第i件物品价值为vi元，重量为wi，假设vi和wi都为整数。他希望带走的东西越值钱越好，但他的背包中之多只能装下W磅的东西，W为一整数。他应该带走哪几样东西？
0-1背包问题中：每件物品或被带走，或被留下，（需要做出0-1选择）。小偷不能只带走某个物品的一部分或带走两次以上同一个物品。
wi vi
a 2 6
b 2 3
c 6 5
d 5 4
e 4 6
w 1 2 3 4 5 6 7 8 9 10
a 0 6 6 9 9 12 12 15 15 15
b 0 3 3 6 6 9 9 9 10 11
c 0 0 0 6 6 6 6 6 10 11
d 0 0 0 6 6 6 6 6 10 10
e 0 0 0 6 6 6 6 6 6 6
这张表是至底向上，从左到右生成的。(a，b，c，d，e五件商品，最多能装10磅的东西，w行表重量，其他行的数字表max价值)
2. 0-1背包问题子结构：
选择一个给定物品i，则需要比较选择i的形成的子问题的最优解与不选择i的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。
3. 伪代码：
4. 编程实现
#include <iostream>
using namespace std;
//物品数据结构
typedef struct commodity
{
int value; //价值
int weight; //重量
}commodity;
const int N = 3; //物品个数
const int W = 50; //背包的容量
//初始物品信息
commodity goods[N+1]={{0,0},{60,10},{100,20},{120,30}};
int select[N+1][W+1];
int max_value();
int main()
{
int maxvalue = max_value();
cout<<"The max value is: ";
cout<<maxvalue<<endl;
int remainspace = W;
//输出所选择的物品列表：
for(int i=N; i>=1; i--)
{
if (remainspace >= goods[i].weight)
{
if ((select[i][remainspace]-select[i-1][remainspace-goods[i].weight]==goods[i].value))
{
cout << "item " << i << " is selected!" << endl;
remainspace = remainspace - goods[i].weight;//如果第i个物品被选择，那么背包剩余容量将减去第i个物品的重量 ;
}
}
}
return 0;
}
int max_value()
{
//初始没有物品时候，背包的价值为0
for(int w=1;w<=W;++w)
select[0][w] = 0;
for(int i=1;i<=N;++i)
{
select[i][0] = 0; //背包容量为0时，最大价值为0
for(int w=1;w<=W;++w)
{
if(goods[i].weight <= w) //当前物品i的重量小于等于w，进行选择
{
if( (goods[i].value + select[i-1][w-goods[i].weight]) > select[i-1][w])
select[i][w] = goods[i].value + select[i-1][w-goods[i].weight];
else
select[i][w] = select[i-1][w];
}
else //当前物品i的重量大于w，不选择
select[i][w] = select[i-1][w];
}
}
return select[N][W]; //最终求得最大值
}
5. 测试结果
image.png
