• 沙里软件

  • ShaliSoft.com [手机站]   办公桌收纳抽屉
  • 首页
  • 博文
  • 演示
  • 管理
  • 用回溯法解决子集和问题【C#版本】

    网络   2016/5/11 13:21:50

    最近在开发某项目,遇到这样一个需求:在一个账单记录的Table中,记录着每张账单及其金额,要求用户输入一个金额,从表中取出金额组合为该金额的账单【可能有很多个解,但只需要提供一例】。

    这题目看起来很简单,只是把数加起来判断,但仔细一想,难度不小。因为组合的个数没有确定,可以直接找到,即1个,或者2个,3个……N个组成,那么原先想要使用的for循环就无法使用了,因为不知道要嵌套多少层,而且跟后来的方法相比效率较低。

    后来在网上查了好久,查到了这原来这叫做子集和问题,是什么0-1背包之类的问题【数据结构学得一般T^T】需要用递归或回溯解决。因为我只需要求出一解,所以我选择了回溯法。递归将显示所有组合,但我并不需要。下面是仿照别人的思路写出的代码,我将一一注释。

    static void Main(string[] args)
    {
      int[] test = { 3, 7, 18, 33, 22, 6, 10, 21, 2, 15 };//测试用的数组
      bool[] flag = { false, false, false, false, false, false, false, false, false, false };//标志数组,与测试数组对应,true代表该数在组合中,false则不在
      Bubble(test);//冒泡,其实不排序也可以
      int target = Convert.ToInt32(Console.Read());
      bool result = BackTrace(test, flag, target);
    
      if (result == true)
      {
        for (int i = 0; i <= test.Length - 1; i++)
        {
        if (flag[i] == true)
        Console.Write("{0}, ", test[i]);
        }
      }
      else
      {
        Console.Write("no sub sets found!");
      }
      Console.WriteLine();
    }
    
      static bool BackTrace(int[] a, bool[] flag, int target)
      {
        int sum = 0;//初始化和
        int index = 0;//初始化索引
        while (index >= 0)//从第一个开始找,循环找,与for相比循环更多次
        {
          if (flag[index] == false)//如果不在组合中,则尝试把它加入
          {
          sum += a[index];
          flag[index] = true;
    
          if (sum == target)//如果加入后组合数与目标数一致,则说明找到组合,如果组合数大于目标数,则将刚才的元素从组合中剔除,如果小于,则什么也不做.同时继续检验下一元素.
          return true;
          else if (sum > target)
            {
            sum -= a[index];
            flag[index] = false;
            }
          index++;//继续检验下一元素
          }
    
        //如果索引到了最后,还没有找到合适的组合,那么将回溯.一般来说会出现*100011或*1000的情况,即此时flag中的元素应该在某个1之后有若干个0或01组合【先0后1】, [I个数] 1 [J个0][K个1]这样的情况,回溯到1的位置,将其变为0,然后继续往下循环检验.从后面回溯的时候,将1变为0,遇0不变.如果回溯到首位,则说明没有合适的组合存在.
    
        if (index >= a.Length)
        {
          while (flag[index - 1] == true)//如果在组合中,则退出,并往前回溯
          {
            flag[index - 1] = false;
            index--;
            sum -= a[index];
            if (index < 1)//此时index最大为0,但下次循环将出界,已经回溯到最开始了
                   return false;
          }
    
          while (flag[index - 1] == false)//如果不在组合中,往前回溯
          {
            index--;
            if (index < 1)
              return false;//此时index最大为0,但下次循环将出界,已经回溯到最开始了
          }
          flag[index - 1] = false;
          sum -= a[index - 1];
        }
    
      }
      return false;
    
      }
    
      static void Bubble(int[] a)
      {
        for (int i = 0; i <= a.Length - 2; i++)
        for (int j = i + 1; j <= a.Length - 1; j++)
        {
          if (a[i] > a[j])
          {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
          }
      }
    
      foreach (int k in a)
      Console.Write("{0}, ", k);
      Console.WriteLine();
    }

    还应注意Console.ReadLine(),读入的是字符串,要经过Convert.ToInt32()的处理,因为输入的是字符串,其值与字面值不一致.

    此外应该还可以再优化,但过几个钟还要上班,还是睡觉去吧.

    PS:我不是通宵工作,我从10点睡到4点半,睡不着就起床写一下博客。程序员要记得劳逸结合哦!


    阅读(3125) 分享(0)

    上一篇: 怎么做秒杀系统?秒杀系统设计
    下一篇: 微信订阅号授权登录,订阅号怎么实现网页授权登录?

  • 精彩推荐

    ◆ Win7的IIS7中ASP获得的系统日期格式为斜杠和去掉星期的解决办法
    ◆ 腾讯OA基础服务使用C# 开发的千万级应用
    ◆ 怎么做秒杀系统?秒杀系统设计
    ◆ 怎么设计比较安全的密码加密方法
    ◆ asp.net 用Stopwatch计算运行时间
    ◆ ASP.NET Eval四种绑定方式
    ◆ 安卓手机QQ新功能WiFi共享泄露用户隐私
    ◆ 我为什么不喜欢面向对象
    ◆ 老照片:马云、马化腾、李彦宏、刘强东、李开复,大佬们的罕见童年照
    ◆ 为什么刷单会被淘宝轻而易举的查到?
  • 用心做事 不能唯利是图

    • 吊儿
    • 用QQ联系我17905772
  • 搜索


  • 最新文章

    • 导出Excel 格式 mso-number-format
    • 服务器iis支持tls1.2,windows server 2008 r2 中IIS启用TLS 1.2(安装SSL后用TLS 1.2)
    • MySQL配置优化
    • EditPlus 添加文件比较工具winmerge
    • 滚动悬浮固定JS特效

  • 热门文章

    • php sso单点登录实现代码
    • 中国菜刀(China chopper) 最新黑客工具
    • redis.conf中文版(基于2.4)
    • 搜索引擎名单大全
    • php图片上传类,支持加水印,生成略缩图

  • 最新图库


  • 最新评论


  • 友情链接

  • 沙里软件

  • 最近访客

    Powered by ShaliSoft.com 豫ICP备13008529号

    免责声明:本站部分内容来源于互联网,转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,不为其版权负责,也不构成任何其他建议。如果发现侵犯版权,联系QQ17905772进行删除。