回溯法求解01背包
用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个（最优）解。例如，对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。该解空间包含对变量的所有可能的0-1赋值。当n=3时，其解空间是{（0，0，0），（0，0，1），（0，1，0），（0，1，1），（1，0，0），（1，0，1），（1，1，0），（1，1，1）} 定义了问题的解空间后，还应将解空间很好的组织起来，使得能用回溯法方便地搜索整个解空间。通常将解空间组织成树或图的形式。
例如，对于n=3时的0-1背包问题，可用一棵完全二叉树表示其解空间，如图5-1所示。
解空间树的第i层到第i+1层表上的标号给出了变量的值。从树根到叶的任一路径表示解空间中的一个元素。例如，从根节点到节点H的路径相应于解空间中的元素（1,1,1）。
确定了解空间的组织结构后，回溯法送开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个考试节点成为活结点，同时也成为当前的扩展节点。在当前的扩展结点处，搜索向纵深方向移至一个新节点。这个新节点就成为新的活结点，并成为当前扩展节点，如果在当前的扩展节点处不能退再向纵深方向移动，则当前扩展节点就成为死节点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展节点。回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的结果解空间中已无活结点为止。
例如，对于n=3时的0-1背包问题，考虑下面的具体实例：w=【16,15,15】，p=【45,25,25】，c=30。从图5-1的根节点开始搜索其解空间。开始时，根节点时唯一的活结点，也是当前的扩展节点。在这个扩展节点处，可以沿纵深方向移至节点B或者节点C。假设选择先移至节点B。此时，节点A和节点B时活结点，节点B成为当前扩展节点。由于选取了w1，股灾节点B处剩余背包容量是r=14，获得的价值为45.从节点B处，可以移至节点D处或E。由于移至节点D至少需要w2=15的背包容量，而现在仅有的背包容量是r=14，故移至节点D导致不可行解。搜索至节点E不需要背包容量，因而是可行的。从而选择移至节点E。此时，E成为新的扩展节点，节点A,B和E是活结点。在节点E处，r=14，获取的价值为45.从节点E处，可以向纵深移至节点J或节点K。移至节点J导致不可行解，而移向节点K是可行的，于是移向节点K，它成为新的扩展节点。由于节点K是叶节点，故可得到一个可行解。这个解相应的价值为45。xi的取值由根节点到叶节点K的路径唯一确定，即x=（1,0,0）。由于在节点K处已不能再向纵深扩展，所以节点K成为死节点。在返回到节点E处。此时在节点E处也没有可扩展的节点，它也成为死节点。
接下来又返回到节点B处。节点B同样也成为死节点，从而节点A再次成为当前扩展节点。节点A还可继续扩展，从而到达节点C。此时，r=30，获取的价值为0。从节点C可移向节点F或节点G。假设移至节点F，它成为新的扩展节点。节点A,C，F是活结点。在节点F处，r=15，获取的价值为25。从节点F向纵深移至节点L处，此时r=0，获取的价值为50.由于L是叶节点，而且是迄今为止找到的获取价值最高的可行解，因此记录这个可行解。节点L不可扩展，我们返回到节点F处。按此方式继续搜索，可搜索遍整个解空间。搜索结束后找到的最好解释相应0-1背包问题的最优解。
#include<stdio.h>
#define max 100
int weight[max];
int value[max];
int n,max_weight,max_value;
int best_answer[max],answer[max];
void print()
{
int i,j,k,l;
printf("+++++++++++++%d++++++++++++\n",max_value);
for(i=1;i<=n;i++)
printf("%d ",best_answer[i]);
printf("\n");
}
void DFS(int level,int current_weight,int current_value)
{
if(level>=n+1)
{
if(current_value>max_value)
{
int i;
max_value = current_value;
for(i=1;i<=n;i++)
best_answer[i] = answer[i];
}
}
else
{
if(current_weight>=weight[level+1])
{
current_weight = current_weight - weight[level+1];
current_value = current_value + value[level+1];
answer[level+1] = 1;
DFS(level+1,current_weight,current_value);
answer[level+1] = 0;
current_weight = current_weight + weight[level+1];
current_value = current_value - value[level+1];
}
DFS(level+1,current_weight,current_value);
}
}
void init()
{
int i,j,k,l;
max_value = 0;
for(i=1;i<=n;i++)
answer[i] = 0;
}
int main()
{
int i,j,k,l;
while(scanf("%d%d",&n,&max_weight)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&weight[i]);
for(j=1;j<=n;j++)
scanf("%d",&value[j]);
init();
DFS(0,max_weight,0);
print();
}
return 0;
}
/*
3 30
16 15 15
45 25 25
5 10
2 2 6 5 4
6 3 5 4 6
*/