我正在处理子集总和问题，需要打印最接近该值的子集总和，如果相等，则只打印该值。仅正整数
如果有多个子集总和与该值相等，
值= 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);
}
}
}
Willem Van O.. 5
您当前的解决方案利用回溯。这种方法的问题是时间复杂度成指数比例。这样做不好：从您输入合理数量的元素（如100多个）开始，程序就注定了失败。
鉴于您的整数列表都是（严格的）正数，更好的方法是使用动态编程。
这个想法是，如果您搜索总和K，则定义的内存最多为列表的2 K +1个元素。最初，所有存储元素（null元素索引除外）均无效，在该元素0中存储空集合。
因此，最初的内存看起来像：
7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> _ 1 -> _ 0 -> []
如果b=8（我们将b=8在此答案的其余部分中使用，但当然仅是示例）。
有_没有（一个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我们发现不存在总和为1的集合，因此我们继续进行，但现在s=2我们已经构造了这种集合。关键是我们的算法不做任何书签，因此第二次加2会导致：
7 -> _ 6 -> _ 5 -> _ 4 -> [2,2] 3 -> _ 2 -> [2] 1 -> _ 0 -> []
现在，人们可以做两件事：对迭代构造了哪些集合进行书签，但这需要额外的工作，或者可以从高到低进行迭代。由于所有整数xi都保证为正，因此我们知道我们不能在downdown集合中“升级”集合。如果我们以正确的方式执行整个迭代，则内存如下所示：
7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> [2] 1 -> _ 0 -> []
如果下一个元素是1，则内存如下所示：
7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> [2,1] 2 -> [2] 1 -> [1] 0 -> []
现在给出下一个元素3，我们终于看到了动态编程的功能：
7 -> _ 6 -> [2,1,3] 5 -> [2,3] 4 -> [1,3] 3 -> [2,1] 2 -> [2] 1 -> [1] 0 -> []
您会注意到我们尚未为3with 构建一个集合[3]，因为已经有这样的集合。这看起来可能并不那么令人印象深刻。但是，所有起源于此的集合[2,1]现在都不会重复，[3]如果使用回溯算法的话，情况就会如此。
在对每个元素执行此操作之后，将为每个索引的内存使用一种方式来创建具有与索引对应的总和的子集，或者null如果无法构造此类子集。现在，您可以简单地查看构造的集合，然后选择最接近K的集合。我们知道，在大多数此类收集不同ķ，因为空收集具有总和为零，因此不同ķ。
可以使用以下算法讲述整个故事：
static ListGetSubset(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交互式外壳）：
$ 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，依此类推。但是问题在于，这将导致计算量大的方法。
您当前的解决方案利用回溯。这种方法的问题是时间复杂度成指数比例。这样做不好：从您输入合理数量的元素（如100多个）开始，程序就注定了失败。
鉴于您的整数列表都是（严格的）正数，更好的方法是使用动态编程。
这个想法是，如果您搜索总和K，则定义的内存最多为列表的2 K +1个元素。最初，所有存储元素（null元素索引除外）均无效，在该元素0中存储空集合。
因此，最初的内存看起来像：
7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> _ 1 -> _ 0 -> []
如果b=8（我们将b=8在此答案的其余部分中使用，但当然仅是示例）。
有_没有（一个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我们发现不存在总和为1的集合，因此我们继续进行，但现在s=2我们已经构造了这种集合。关键是我们的算法不做任何书签，因此第二次加2会导致：
7 -> _ 6 -> _ 5 -> _ 4 -> [2,2] 3 -> _ 2 -> [2] 1 -> _ 0 -> []
现在，人们可以做两件事：对迭代构造了哪些集合进行书签，但这需要额外的工作，或者可以从高到低进行迭代。由于所有整数xi都保证为正，因此我们知道我们不能在downdown集合中“升级”集合。如果我们以正确的方式执行整个迭代，则内存如下所示：
7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> _ 2 -> [2] 1 -> _ 0 -> []
如果下一个元素是1，则内存如下所示：
7 -> _ 6 -> _ 5 -> _ 4 -> _ 3 -> [2,1] 2 -> [2] 1 -> [1] 0 -> []
现在给出下一个元素3，我们终于看到了动态编程的功能：
7 -> _ 6 -> [2,1,3] 5 -> [2,3] 4 -> [1,3] 3 -> [2,1] 2 -> [2] 1 -> [1] 0 -> []
您会注意到我们尚未为3with 构建一个集合[3]，因为已经有这样的集合。这看起来可能并不那么令人印象深刻。但是，所有起源于此的集合[2,1]现在都不会重复，[3]如果使用回溯算法的话，情况就会如此。
在对每个元素执行此操作之后，将为每个索引的内存使用一种方式来创建具有与索引对应的总和的子集，或者null如果无法构造此类子集。现在，您可以简单地查看构造的集合，然后选择最接近K的集合。我们知道，在大多数此类收集不同ķ，因为空收集具有总和为零，因此不同ķ。
可以使用以下算法讲述整个故事：
static ListGetSubset(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交互式外壳）：
$ 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，依此类推。但是问题在于，这将导致计算量大的方法。
京公网安备 11010802040832号 | 京ICP备19059560号-6 