找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 2725|回复: 0

子集合数问题的回溯解法

[复制链接]
发表于 2014-7-26 17:08:04 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×
    这几天学回溯法,稍微有点心得了,其实就是按深度优先遍历问题解树,而分支界限法则是按广度优先遍历
    给定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)  但是由于分支裁剪以后,下面的子树都不用遍历了,所以复杂度应该远小于这个
下面是我的代码:
  1. // sumofsub.cpp : Defines the entry point for the console application.
  2. //
  3. #include <stdio.h>

  4. int main(int argc, char* argv[])
  5. {
  6.         int arr[6]={5,10,12,13,15,18};
  7.         int x[6]={0,0,0,0,0,0};//0:左子树没走过 1:左子树走过,右子树没走过 2:左子树走过,右子树走过
  8.         int sum=30;
  9.         int totalsum=0;
  10.         int n=6;
  11.         for(int i=0;i<n;i++)
  12.         {
  13.                 totalsum+=arr[i];
  14.         }

  15.         int layer=0;

  16.         while(layer>=0)
  17.         {
  18.                 if(totalsum >= sum)
  19.                 {
  20.                         if(arr[layer] == sum)
  21.                         {
  22.                                 for(int i=0;i<layer;i++)
  23.                                 {
  24.                                         if(x[i] == 1)
  25.                                                 printf("%d ",arr[i]);
  26.                                 }
  27.                                 printf("%d\n",arr[layer]);
  28.                                 x[layer]=2;
  29.                         }
  30.                         else if(arr[layer] < sum && x[layer] != 2)
  31.                         {//走左子树
  32.                                 if(x[layer] == 0)//如果左子树没走过,走左子树
  33.                                 {
  34.                                         x[layer]=1;
  35.                                         sum -= arr[layer];
  36.                                 }
  37.                                 else
  38.                                 {
  39.                                         x[layer]=2;
  40.                                         x[layer+1]=0;
  41.                                 }
  42.                                 totalsum -= arr[layer];
  43.                                 layer++;
  44.                                 continue;
  45.                         }
  46.                         else
  47.                         {
  48.                                 x[layer]=2;
  49.                         }
  50.                 }
  51.                 else
  52.                 {
  53.                         x[layer]=2;
  54.                 }

  55.                 if(x[layer] == 2)
  56.                 {
  57.                         //向上层回溯
  58.                         layer--;
  59.                         if(layer>=0)
  60.                         {
  61.                                 if(x[layer] < 2)
  62.                                         sum += arr[layer];
  63.                                 totalsum += arr[layer];
  64.                         }
  65.                 }
  66.         }

  67.         getchar();
  68.         return 0;
  69. }
复制代码
回复

使用道具 举报

本版积分规则

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-11-23 21:39 , Processed in 0.028085 second(s), 21 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表