用回溯法解决子集和问题【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点半,睡不着就起床写一下博客。程序员要记得劳逸结合哦！

阅读(3102) 分享(0)

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