子集合数问题的回溯解法
这几天学回溯法，稍微有点心得了，其实就是按深度优先遍历问题解树，而分支界限法则是按广度优先遍历给定n=4 W={11,13,24,7} M=31 则子集合数问题的解为X={0,0,1,1} 和X={1,1,0,1}
X只能取{0 1}，相应地是选或者不选该数，按照选和不选，就可以构造一颗解树，利用回溯法遍历该树。
复杂度本应该是O(2^n)但是由于分支裁剪以后，下面的子树都不用遍历了，所以复杂度应该远小于这个
下面是我的代码：
// sumofsub.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
int main(int argc, char* argv[])
{
int arr={5,10,12,13,15,18};
int x={0,0,0,0,0,0};//0:左子树没走过 1:左子树走过，右子树没走过 2:左子树走过，右子树走过
int sum=30;
int totalsum=0;
int n=6;
for(int i=0;i<n;i++)
{
totalsum+=arr;
}
int layer=0;
while(layer>=0)
{
if(totalsum >= sum)
{
if(arr == sum)
{
for(int i=0;i<layer;i++)
{
if(x == 1)
printf("%d ",arr);
}
printf("%d\n",arr);
x=2;
}
else if(arr < sum && x != 2)
{//走左子树
if(x == 0)//如果左子树没走过,走左子树
{
x=1;
sum -= arr;
}
else
{
x=2;
x=0;
}
totalsum -= arr;
layer++;
continue;
}
else
{
x=2;
}
}
else
{
x=2;
}
if(x == 2)
{
//向上层回溯
layer--;
if(layer>=0)
{
if(x < 2)
sum += arr;
totalsum += arr;
}
}
}
getchar();
return 0;
}
页:
[1]