问题描述：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
思路：（深度搜索）
从第一个物品开始放进背包，如果能放下，继续放下一个物品，如果放不下，忽略本物品，放下一个物品。
思路很简单，下面是用递归实现的代码：下面给了两个例子来验证结果
#include <iostream>
using namespace std;
const int n = 5; //假设5个物品
int weight[5]; //存放5个物品的重量
int value[5]; //存放5个物品的价值
int select[5]; //表示每个物品是否放入，0代表没有放入，1代表放入背包
int temp_select[5]; //临时数组，跟踪使价值最大时的放入方案
int WEIGHT = 10;
//int WEIGHT = 8; //例1
int temp_value = 0;
void dfs(int k, int t_v, int t_w) //从第k件物品开始搜索
{
if (k == n) return; //出口，当k物品已经超过最后一件时，退出
for (int i = k; i < n; ++i) //从第k件物品开始向后搜索
{
if (t_w + weight[i] <= WEIGHT) //如果加上第i件物品可以装下
{
select[i] = 1; //第i件物品选中，为t_v -= value[k] t_w -= weight[k]提供分辨
t_w += weight[i]; //得到现在的重量
t_v += value[i]; //得到现在的价值
if (t_v>temp_value) //如果比原来纪录最大的价值还大
{
for (int j = 0; j < 5; ++j){
temp_select[j] = select[j];//把选中哪个的方案拷贝进临时数组中
}
temp_value = t_v;
}
dfs(i + 1, t_v, t_w); //继续从下一件物品开始搜索
}
else dfs(i + 1, t_v, t_w); //如果第i件装不下 //就装第i+1件
//第i个物品后面所有的装包方案已经遍历完成
if (select[i] == 1) //如果k个装进去了，需要拿出来，下面价值和重量都做减法
{
select[i] = 0; //此时，该退出第k个，即第k个装包所有情况遍历完成
t_v -= value[i];
t_w -= weight[i];
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//例1
/*weight[0] = 5;
weight[1] = 2;
weight[2] = 1;
weight[3] = 1;
weight[4] = 6;
value[0] = 40;
value[1] = 12;
value[2] = 7;
value[3] = 8;
value[4] = 48;*/
weight[0] = 2;
weight[1] = 2;
weight[2] = 6;
weight[3] = 5;
weight[4] = 4;
value[0] = 6;
value[1] = 3;
value[2] = 5;
value[3] = 4;
value[4] = 6;
dfs(0, 0, 0); //给一个入口遍历
for (int i = 0; i < 5; i++)
cout << temp_select[i] << endl;
cout << temp_value << endl;
return 0;
}
结果：
上述思路很简单，理解较为简单，难在
if (select[i] == 1) //如果k个装进去了，需要拿出来，下面价值和重量都做减法
{
select[i] = 0; //此时，该退出第k个，即第k个装包所有情况遍历完成
t_v -= value[i];
t_w -= weight[i];
} 这一步应该放在哪个位置。第i个物品的循环，结束后应该是第i+1件物品进行递归循环，如果第i件物品是建立在放进背包的基础上的，那么需要置选择状态为0，总价值和总重量减去第i件物品的重量和价值。如果第i件物品没有放进背包，即select[i] == 0，那么不影响，直接进行i+1件物品的循环。（
注：第i件物品的递归，一定会遍历完第i+1到第n件物品的所有状态
）