-
用回溯法解决子集和问题【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点半,睡不着就起床写一下博客。程序员要记得劳逸结合哦!
阅读(2863) 分享(0)
上一篇: 怎么做秒杀系统?秒杀系统设计
下一篇: 微信订阅号授权登录,订阅号怎么实现网页授权登录?