首页 博文

用回溯法解决子集和问题【C#版本】

2016-5-11 13:21:50 网络 A+

最近在开发某项目,遇到这样一个需求:在一个账单记录的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点半,睡不着就起床写一下博客。程序员要记得劳逸结合哦!


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