查找最小的子集和匹配的另一子集和 [英] Find smallest subset sum matching another subset sum

问题描述

我有一个实际问题（未作业！），需要寻找集合A的等于一些其他集合B的子集的总和的一个子集的总和。

I have a real-world problem (not homework!) that requires finding the sum of a subset of set A that equals the sum of a subset of some other set B.

与有用的答案<一个非常类似的问题href="http://stackoverflow.com/questions/443712/algorithm-to-find-subset-within-two-sets-of-integers-whose-sums-match">is这里。

考虑这个例子：

@a = qw(200 2000 2000 2000 4000);
@b = qw(528 565 800 1435 2000 2000 2872);

使用<一个href="http://stackoverflow.com/questions/443712/algorithm-to-find-subset-within-two-sets-of-integers-whose-sums-match/443950#443950">the对这个问题提供了答案接受code ，我得到以下的输出：

Using the code provided in the accepted answer to that question, I get the following output:

sum(200 2000 4000) = sum(528 800 2000 2872)
sum(200 4000 4000) = sum(528 800 2000 2000 2872)
sum(200 4000) = sum(528 800 2872)
sum(200 2000 2000 2000 4000) = sum(528 800 2000 2000 2000 2872)

对于我而言，我只想要使用的输入集合的元素最少的答案（S）。在这个例子中，我只是想

For my purposes, I only want the answer(s) that use the fewest elements of the input sets. In this example, I just want

sum(200 4000) = sum(528 800 2872)

由于所有其他的答案也有 200 和 4000 的总和。也就是说，我正在寻找只是简单可能的和（在这个意义上，他们用最少的元素）。有人建议可以这样做的一个相当有效的方法？ （蛮力是好的，因为我的数组没有那么大。）

because all of the other answers also have 200 and 4000 in the sum. That is, I'm looking for just the "simplest" possible sums (in the sense that they use the fewest elements). Can someone suggest a reasonably efficient way of doing this? (Brute force is okay as my arrays aren't that large.)

另外，我要指出，在输出的第二行，和（200 4000 4000）... ，是不正确的，因为 4000 中只出现一次 @a 。我怕我不明白的算法不够好，看看为什么会这样。

Also, I should note that the second line of the output, sum(200 4000 4000) ..., isn't correct because 4000 only appears once in @a. I'm afraid I don't understand the algorithm well enough to see why this is happening.

任何帮助，无论是这些将是非常美联社preciated！

Any help with either of these would be much appreciated!

推荐答案

这个问题是NP完全问题，因此除非P = NP你坚持做指数工作，对输入的大小。现在的妙处这种类型的问题是，实际上有两种方法可以解决这将给指数对这一问题的不同方面。

This problem is NP-complete, so unless P=NP you are stuck doing exponential work on the size of the input. Now the neat thing about this type of problem is that there are actually two ways to solve which will put the exponent on different aspects of the problem.

首先，如果你的款项没有太多的元素，你可以只是蛮力这个问题通过搜索在所有组合。此方法是指数在套元件的数量，并且将工作相当好高达说每个容器20左右的元件。之后，它是会得到pretty的讨厌。

First if your sums don't have too many elements you can just brute force this problem by searching over all combinations. This method is exponential on the number of elements in the sets, and will work reasonably well up to say 20 or so elements per container. After that it is going to get pretty nasty.

第二个选择是使用动态规划。不像previous方法，该算法是指数的，因为它需要写出来的每一个号码的位数。你要做的就是保持集中的所有可能的款项，以及最小的数字生成它们所需元素的轨道。这是你在​​你的答案链接到溶液的一个简单的修改

A second option is to use dynamic programming. Unlike the previous method, this algorithm is exponential in the number of bits that it takes to write out each of the numbers. What you do is keep track of the set of all possible sums as well as the smallest number of elements required to generate them. This is a simple modification of the solution that you linked to in your answer.

下面是一些Python code产生的所有他们可以相交的可能值：

Here is some python code that generates all the possible values they can intersect at:

    def gen_sum(a):
        r = { 0: [] }
        for x in a:
            for y, v in r.items():
                if not (x+y) in r or len(r[x+y]) > len(v) + 1:
                    r[x+y] = v + [x]
        return r

    def gen_sums(a, b):
        asum = gen_sum(a)
        bsum = gen_sum(b)
        return [ (k, v, bsum[k]) for k,v in asum.items() if k in bsum ][1:]

在你的样本数据运行它，我得到了：

Running it on your sample data, I got:

[（4000，[4000]，[2000，2000），（6000，[2000,4000]，[565，1435，2000，2000），（2000，[2000]，[2000]）， （4200，[200，4000]，[528，800，2872]），（10200，[200，2000，2000，2000，4000]，[528，565，800，1435，2000，2000，2872]）， （8200，[200，2000，2000，4000]，[528，800，2000，2000，2872]），（6200，[200，2000，4000]，[528，800，2000，2872]）]

[(4000, [4000], [2000, 2000]), (6000, [2000, 4000], [565, 1435, 2000, 2000]), (2000, [2000], [2000]), (4200, [200, 4000], [528, 800, 2872]), (10200, [200, 2000, 2000, 2000, 4000], [528, 565, 800, 1435, 2000, 2000, 2872]), (8200, [200, 2000, 2000, 4000], [528, 800, 2000, 2000, 2872]), (6200, [200, 2000, 4000], [528, 800, 2000, 2872])]

编辑：修正了一个错字，也只注意到人哇靠吨已经回答了这个非常快

Fixed a typo, and also just noticed that holy crap tons of people have already answered this really quick.

这篇关于查找最小的子集和匹配的另一子集和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！