如果没有子集和等于给定值，则返回最接近该值的子集和

我正在研究子集求和问题，需要打印最接近该值的子集和，如果相等则只打印该值。 只有正整数

如果有多个子集和等于该值，

value = 10，subsetSum1 = 9，subsetSum2 = 11

打印小于该值的总和。

因此，控制台应用程序可以完美地找到相等的子集和，但是如何打印出最接近该值的子集和。

class Program { static int[] elements; static int value; static bool solution = false; static void Main() { value = 10000; Console.WriteLine("How many numbers ?"); int elementsQty = int.Parse(Console.ReadLine()); elements = new int[elementsQty]; for (int i = 0; i < elementsQty; i++) { elements[i] = int.Parse(Console.ReadLine()); } Console.WriteLine("\nOutput:"); List subset = new List(); GetSubset(0, subset); if (!solution) Console.WriteLine("No match"); Console.ReadLine(); } static void GetSubset(int index, List myElements) { if (myElements.Sum() == value && myElements.Count > 0) { Console.WriteLine(" {0} = {1}", string.Join(" + ", myElements), value); solution = true; } for (int i = index; i < elements.Length; i++) { myElements.Add(elements[i]); GetSubset(i + 1, myElements); myElements.RemoveAt(myElements.Count - 1); } } } 

Answer 1

您当前的解决方案使用回溯 。 这种方法的问题在于时间复杂度呈指数级增长。 哪个不好：从您输入合理数量的元素（如100+）开始，您的程序就注定失败了。

鉴于您的整数列表都是（严格）正数，更好的方法是使用动态编程 。

这个想法是，如果你搜索一个和K ，你定义一个最多2 K + 1个列表元素的内存 。 最初所有内存元素都是无效null ，除了元素索引0 ，您存储空集合。

所以最初的内存看起来像：

 7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> _ 1 -> _ 0 -> [] 

如果b=8 （我们将在本答案的其余部分使用b=8 ，但它当然只是一个例子）。

with _ nothing（ null指针）和[]空集合（不管是什么类型的集合）。

现在，对于给定数字集中的每个元素，执行以下任务。 迭代内存中的所有有效（非null ）集合。 对于每个集合，您“升级”该集合：创建副本，将元素添加到集合中，并使用新总和将其存储到索引中。 如果已经存在具有该总和的集合，则不执行任何操作。 这种迭代可以如下实现：

 for(int s = b-xi-1; s >= 0; s--) { if(cols[s+xi] == null && cols[s] != null) { List cln = new List(cols[s]); cln.Add(xi); cols[s+xi] = cln; } } 

用xi我们想要添加的元素。 因此， if语句检查具有sum s的集合是否有效（非null ）以及是否必须创建新集合：具有结果总和的集合是否尚不存在。 for循环设置边界：将集合升级为边界是没有用的：因此s+xi和s必须是有效边界。 这意味着s的范围从0 （包括）到b-xi-1 （包括）。 我们必须向后迭代，因为否则我们可以第二次添加元素xi 。

实际上，以第一个元素为2为例，现在我们开始从0到8-2-1=5迭代（错误地）。 现在这意味着如果s=0 ，我们“升级”空集合，所以现在内存看起来像：

 7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> [2] 1 -> _ 0 -> [] 

（ [2]是一个带有2的集合）， for循环的下一次迭代， s=1 ，我们看不到存在和的一个集合，所以我们继续，但现在s=2 ，我们刚刚构建了这样的集合。 关键是我们的算法没有做任何书签，因此将第二次添加2，导致：

 7 -> _ 6 -> _ 5 -> _ 4 -> [2,2] 3 -> _ 2 -> [2] 1 -> _ 0 -> [] 

现在可以做两件事：为迭代构建哪些集合做书签，但这需要额外的工作，或者可以从高到低迭代。 由于所有整数xi都保证是正数，我们知道我们无法“升级”向下集合中的集合。 如果我们以正确的方式执行整个迭代，之后内存看起来像：

 7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> [2] 1 -> _ 0 -> [] 

如果下一个元素是1 ，则内存如下所示：

 7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> [2,1] 2 -> [2] 1 -> [1] 0 -> [] 

现在给出下一个元素是3 ，我们终于看到了动态编程的强大function：

 7 -> _ 6 -> [2,1,3] 5 -> [2,3] 4 -> [1,3] 3 -> [2,1] 2 -> [2] 1 -> [1] 0 -> [] 

你注意到我们还没有为[3]构建一个3的集合，因为已经存在这样的集合。 这可能看起来不那么令人印象深刻。 但是，所有源自[2,1]集合现在都不会与[3]重复，如果使用回溯算法则会出现这种情况。

在为每个元素执行此操作之后，每个索引的内存要么是创建具有与索引对应的总和的子集的方式，要么是如果不能构造这样的子集则为null 。 现在，您只需查看构造的集合，然后选择最接近K的集合。 我们知道这样的集合最多不同于K ，因为空集合的总和为零，因此K不同。

可以使用此算法讲述整个​​故事：

 static List GetSubset(int value, IEnumerable xs) { int b = 2*value; List[] cols = new List[b]; cols[0] = new List(); foreach(int xi in xs) { for(int s = b-xi-1; s >= 0; s--) { if(cols[s+xi] == null && cols[s] != null) { List cln = new List(cols[s]); cln.Add(xi); cols[s+xi] = cln; } } } for(int d = 0; d < value; d++) { if(cols[value-d] != null) { return cols[value-d]; } else if(cols[value+d] != null) { return cols[value+d]; } } return cols[0]; } 

List方法效率不高：您可以使用头尾列表方法（但不幸的是，.NET库似乎缺乏此方法）。

演示 （使用csharp交互式shell）：

 $ csharp Mono C# Shell, type "help;" for help Enter statements below. csharp> public class Foo { > > public static List GetSubset(int value, IEnumerable xs) { > int b = 2*value; > List[] cols = new List[b]; > cols[0] = new List(); > foreach(int xi in xs) { > for(int s = b-xi-1; s >= 0; s--) { > if(cols[s+xi] == null && cols[s] != null) { > List cln = new List(cols[s]); > cln.Add(xi); > cols[s+xi] = cln; > } > } > } > for(int d = 0; d < value; d++) { > if(cols[value-d] != null) { > return cols[value-d]; > } else if(cols[value+d] != null) { > return cols[value+d]; > } > } > return cols[0]; > } > } csharp> csharp> int[] items = new int[] {2,3,5,7}; csharp> Foo.GetSubset(8,items); { 3, 5 } csharp> Foo.GetSubset(7,items); { 2, 5 } csharp> Foo.GetSubset(9,items); { 2, 7 } csharp> Foo.GetSubset(6,items); { 2, 3 } csharp> Foo.GetSubset(10,items); { 2, 3, 5 } csharp> Foo.GetSubset(11,items); { 2, 3, 5 } 

正如你所看到的那样， 6不能用这些整数形成，但是可以想出一个总和最多为5的集合。

这种方法的一个优点是你只需要进行一次搜索：你可以多次调用你的方法，首先搜索值K ，然后是K + 1 ，然后是K-1等。 但问题是这将导致计算上昂贵的方法。