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

本文关键字：子集 返回 最接近 如果没有 | 更新日期: 2023-09-27 18:26:15

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

如果有多个子集和同样接近该值，

value=10，subsetSum1=9，subsetSumm2=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<int> subset = new List<int>();
            GetSubset(0, subset);
            if (!solution)
                Console.WriteLine("No match");
            Console.ReadLine();
        }
        static void GetSubset(int index, List<int> 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);
            }
        }
    }

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

您当前的解决方案使用回溯。这种方法的问题在于时间复杂性是指数级的。这是不好的：从你输入合理数量的元素（比如100+）的那一刻起，你的程序就注定要失败。

如果你的整数列表都是（严格）正的，那么更好的方法是使用动态编程。

其思想是，如果搜索一个和K，则定义一个最多包含2K+1列表元素的内存。最初，除了存储空集合的元素索引0之外，所有内存元素都是无效的null。

所以最初的记忆看起来像：

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<int> cln = new List<int>(cols[s]);
        cln.Add(xi);
        cols[s+xi] = cln;
    }
}

其中CCD_ 9是我们希望添加的元素。因此，if语句检查总和为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都保证为正，我们知道我们不能"升级"向下集合中的集合。如果我们以正确的方式执行整个迭代，那么之后的内存看起来像：

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 -> []

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

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

整个故事可以用这个算法来讲述：

static List<int> GetSubset(int value, IEnumerable<int> xs) {
    int b = 2*value;
    List<int>[] cols = new List<int>[b];
    cols[0] = new List<int>();
    foreach(int xi in xs) {
        for(int s = b-xi-1; s >= 0; s--) {
            if(cols[s+xi] == null && cols[s] != null) {
                List<int> cln = new List<int>(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<T>方法不是最有效的：您可以使用头尾列表方法（但不幸的是，.NET库似乎缺少这一点）。

演示（使用csharp交互式外壳）：

$ csharp
Mono C# Shell, type "help;" for help
Enter statements below.
csharp> public class Foo {
      >  
      > public static List<int> GetSubset(int value, IEnumerable<int> xs) {
      >         int b = 2*value;
      >         List<int>[] cols = new List<int>[b];
      >         cols[0] = new List<int>();
      >         foreach(int xi in xs) {
      >             for(int s = b-xi-1; s >= 0; s--) {
      >                 if(cols[s+xi] == null && cols[s] != null) {
      >                     List<int> cln = new List<int>(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等。但问题是，这将导致计算成本高昂的方法。

相关文章：