解释这个子集求和函数

Question

这段代码是解决子集和问题变体的函数，但我不太明白它是如何得到答案的。

函数return是最接近该值的子集总和，如果它与该值相同则它只是return该值，如果两个子集总和同样接近该值然后 return 较大的总和。

就是这个

public static List<int> SolveSubsetSum(int value, IEnumerable<int> xs) 
{
    int b = 2*value+1;
    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];
}

我理解标准的东西，但我不知道循环中发生了什么。

我的主要问题是

为什么它需要一个 2*value+1 集合的数组？
循环中发生了什么？

Answer 1

不知何故，您问题中的代码是实现此算法的 (my¹) answer 的精确副本。我同意算法本身并不新鲜，但是代码的结构和变量都表明复制。如果您仔细阅读了问题（和答案），您可能会发现正在解决的问题是 closest 子集和问题。这意味着如果无法构建这样的集合，您 return 具有最小差异的集合。

现在因为这样的集合可以大于，所以你最多需要2 K+1 collection使用 K 请求的数字，因为您的 collection 中的最小数字可能是 K-1。例如，给定的数字是 {2,5,8,10}，你希望构建 6 的子集，而不是最近的子集总和是 {2,5}。您需要足够 "collections" 来存储更大的子集。

循环中发生的事情在链接的答案中进行了解释。

¹谁写的答案无关紧要，但更容易发现自己的作品。

解释这个子集求和函数

Explain this subset sum solving function

c#

algorithm

subset-sum