说明此子集和解功能 [英] Explain this subset sum solving function

问题描述

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

This chunk of code is the function that solves a variant of a subset sum problem, but I dont really understand how it gets the answer.

该函数返回最接近该值的子集和，如果它与该值相同，则仅返回该值，如果两个子集和与该值相等，则返回更大的和.

The function returns the subset sum that's closest to the value, if its the same as the value then it just return the value, if two subsets sums are equally close to the value then return the greater sum.

就这样

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

我了解标准内容，但是我不知道循环中发生了什么.

I understand the standard stuff, but I have no clue whats going on in the loops.

我的主要问题是

• 为什么需要一个由2*value+1个集合组成的数组?

循环中发生了什么?

推荐答案

以某种方式，您问题中的代码是该代码的精确副本(my ¹ )

Somehow, the code in your question is an exact copy of this (my¹) answer that implemented this algorithm. I agree that the algorithm itself is not new, but both the structure of the code as well as the variables indicate copying. If you had read the question (and answer) carefully, you could have found out that the problem being solved is the closest subset sum problem. This means that in case no such set can be constructed, you return the set with the smallest difference.

现在，由于这样的集合可以更大到所请求的总和，因此您最多需要 2 K + 1 个集合，并带有 K 个请求的数字，因为您的收藏夹中最小的数字可能是 K-1 .假设给定的数字为{2,5,8,10}，并且您希望构造6的子集，而最近的子集总和为{2,5}.您需要足够的集合"来存储更大的子集.

Now since such set can be larger that the requested sum, you need at most 2 K+1 collections with K the requested number, because it is possible that the smallest number in your collection is K-1. Say for instance that the given numbers are {2,5,8,10} and you wish to construct a subset of 6, than the nearest subset sum is {2,5}. You need enough "collections" to store subsets that can be larger.

链接的答案中说明了循环中发生的事情.

What's going on in the loops is explain in the linked answer.

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

¹ Who wrote the answer is irrelevant, nevertheless is it easier to detect your own work.

这篇关于说明此子集和解功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！