如果没有子集和等于给定值，return个子集和最接近该值

Question

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

如果有多个子集和与该值的接近程度相等，

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<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);
            }
        }
    }

Answer 1

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

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

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

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

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

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

with _ nothing (a null pointer), and [] an empty collection (不管是哪种集合).

现在，对于给定数字集中的每个元素，您执行以下任务。您迭代内存中的所有有效（不是 null）集合。对于每个集合，你 "upgrade" 那个集合：你制作一个副本，将元素添加到集合中，然后将它与新的总和一起存储到索引中。如果已经有一个包含该总和的集合，则您什么都不做。这样的迭代可以实现如下：

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;
    }
}

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

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

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 都保证为正数，我们知道我们不能 "upgrade" 向下集合中的集合。如果我们以正确的方式执行整个迭代，之后的内存如下所示：

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> 方法不是最有效的：您可以使用 head-tail 列表方法（但不幸的是，.NET 库似乎缺少此方法） .

演示（使用csharp交互shell）：

$ 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，等等。但问题是这将导致计算量大的方法。

如果没有子集和等于给定值，return个子集和最接近该值

If there is no subset sum equal to a given value, return subset sum closest to the value

c#

algorithm

subset-sum