2

我有一个现实世界的问题（不是家庭作业！），需要找到集合 A 的子集的总和，它等于其他集合 B 的子集的总和。

一个非常相似的问题有一个有用的答案是here。

考虑这个例子：

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

使用该问题的已接受答案中提供的代码，我得到以下输出：

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)

出于我的目的，我只想要使用输入集中元素最少的答案。在这个例子中，我只想

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

因为所有其他答案也有200和4000。也就是说，我正在寻找“最简单”的可能总和（从某种意义上说，它们使用最少的元素）。有人可以提出一种合理有效的方法吗？（蛮力是可以的，因为我的阵列不是那么大。）

另外，我应该注意输出的第二行sum(200 4000 4000) ..., 是不正确的，因为4000只在@a. 恐怕我对算法的理解不够深入，无法理解为什么会发生这种情况。

任何对其中任何一个的帮助将不胜感激！

4

4 回答 4

3

这个问题是 NP 完全的，所以除非 P=NP，否则你会被困在对输入大小做指数工作。现在关于这类问题的巧妙之处在于，实际上有两种解决方法，它们会将指数放在问题的不同方面。

首先，如果您的总和没有太多元素，您可以通过搜索所有组合来强制解决这个问题。这种方法在集合中的元素数量上呈指数增长，并且在每个容器最多 20 个元素的情况下工作得相当好。在那之后它会变得非常讨厌。

第二种选择是使用动态规划。与以前的方法不同，该算法在写出每个数字所需的位数上呈指数级增长。您所做的是跟踪所有可能总和的集合以及生成它们所需的最少元素数量。这是您在答案中链接到的解决方案的简单修改。

这是一些 python 代码，它生成它们可以相交的所有可能值：

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

在您的示例数据上运行它，我得到：

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

编辑：修正了一个错字，并且刚刚注意到很多人已经很快回答了这个问题。

于 2011-06-22T18:36:18.123 回答
1

您需要修改递归关系，而不仅仅是输出。考虑{1,2,20,23,42}和{45}。原始算法将输出 {1,2,42},{45} 而不是 {20,23},{45}。这是因为 42 被认为是最后一个，当它总和为 45 时，它将覆盖之前包含 {20,23} 的 45 处的桶值

而不是为每个值保留 [set,sum]，您需要保留 [ minimum set, sum ]，然后在最后取最小值。

我的 perl 很糟糕，但是像这样

$a{$m+$a} = [min-length(@{$a{$m}},$a{$m+$a}[0]),$a];

其中 min-length 返回较小的集合

于 2011-06-22T18:21:48.013 回答
1

这是一个更新的算法，它给出了所有的总和：

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

my %a = sums( @a );
my %b = sums( @b );

for my $m ( keys %a ) {
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n" if exists $b{$m};
}

sub sums {
    my( @a ) = @_;

    return () unless @a;

    my %a;

    while( @a ) {
        $a = shift @a;

        for my $m ( keys %a ) {
            $a{$m+$a} = [@{$a{$m}},$a];
        }

        $a{$a} = [$a];
    }

    return %a;
}

您所要做的就是找到最短的，但其他人已经涵盖了:)

高温下，

保罗

于 2011-06-22T18:30:02.600 回答
0

我对 perl 不是很好。但，

for $m ( keys %a ) {
print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n" if exists $b{$m};

}

修改此行以计算集合 $a 和 $b 中每个 $m 的元素数。完成所有这些循环后，选择元素数量最少的一个。

于 2011-06-22T17:57:13.907 回答