问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。 摘自百度百科
对于回溯的思想，抓住两点一个是组织解空间， 一个是用DFS搜索解空间
相对于0-1背包问题，这种数据求集合的子集之类的问题，固有的思维方式就是建造解空间为一颗子集树（一个完全平衡二叉树）
子集树的特点就是所有的子集都是问题的解，而这些节都是在这个树的叶子结点上。
既然知道了解空间 ， 那么就可以实施第点了，就是根据这颗树得到每个叶子结点的值，当然是用DFS啦！
现在来说说n-1背包问题：
上图是处理abcd四个物品放入包中的解集，直接上回溯算法的代码
-
#include "stdafx.h"
-
#include <string>
-
using namespace std;
-
#define GOODNUMBER 4
-
#define BAGWIGHT 15
-
typedef struct
-
{
-
int w;
-
int v;
-
string name;
-
int visit;
-
}GOODS;
-
-
GOODS x[GOODNUMBER] = {0};
-
int allwight = 0;
-
int allValue = 0;
-
void backtrack(int t)
-
{
-
if (t == GOODNUMBER)
-
{
-
//到了叶子结点
-
printf("Value is %d\n",allValue);
-
return;
-
}
-
if((x[t].w + allwight) <= BAGWIGHT) //进入左子树
-
{
-
allwight += x[t].w;
-
allValue += x[t].v;
-
x[t].visit = 1;
-
backtrack(t + 1);
-
allwight -= x[t].w;
-
allValue -= x[t].v;
-
x[t].visit = 0;
-
}
-
if (x[t].visit == 0)
-
{
-
backtrack(t + 1); //进入右子树
-
}
-
-
}
-
-
int _tmain(int argc, _TCHAR* argv[])
-
{
-
GOODS A = { 7, 5, "A" };
-
GOODS B = { 3, 1, "B" };
-
GOODS C = { 5, 8, "C" };
-
GOODS D = { 8, 4, "D" };
-
x[0] = A;
-
x[1] = B;
-
x[2] = C;
-
x[3] = D;
-
backtrack(0);
-
getchar();
-
return 0;
-
}
