01背包问题(用c语言实现)-回溯法求解

时间:2022-09-20 18:42:40

01背包问题(用c语言实现)-回溯法求解

回溯法求解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


*/