寻找数字组合，使它们的和等于目标数字。

Question

寻找数字组合，使它们的和等于目标数字。

4

我需要一个算法，能够识别一组数字的所有可能组合，使它们的和等于另一个数字。

例如，给定集合{2,3,4,7}，我需要知道所有可能的子集，使它们的和为x。如果x == 12，答案是{2,3,7}；如果x == 7，答案是{{3,4},{7}}（即两个可能的答案）；如果x == 8，则没有答案。请注意，如这些示例所示，集合中的数字不能重复使用。

这个问题几年前在这个网站上提出过，但答案是用C#编写的，我需要用Perl来实现，但不知道如何翻译答案。

我知道这个问题很难（请参见其他帖子进行讨论），但我只需要一种暴力解决方案，因为我处理的数据集非常小。

- itzy

2

你最后一段说得很好。了解哪些运行时是可接受的总是至关重要的。 - ShreevatsaR

请注意，正如这些示例所暗示的那样，集合中的数字不能被重复使用。因此，如果您有 {2,3,4,6,9} 和 x==11，那么您不能有 {{2,3,6},{2,9}}，因为重复使用了 2。或者，通过“集合”您是指“子集”？ - vol7ron

@vol7ron，他的意思是你的例子中{2,3,3,3}不是一个有效的答案，因为你每个子集只能使用3一次。 - cjm

@cjm：我也是这么想的，但不同的组合游戏有不同的规则。 - vol7ron

@vol7ron，@cjm是正确的。对于我需要解决的问题，集合中的每个数字只能使用一次。 - itzy

@itzy：它不是一个集合，而是一个子集。您返回一个结果集，由一对多个数字集组成。您所指的内部集是子集。 -- 无论如何，就递归和大多数可能的结果而言，这都使事情变得更容易。 - vol7ron

6个回答

1

使用算法::组合数学。这样，您可以预先确定要考虑的子集大小，并将内存使用保持到最小。应用一些启发式方法以提前返回。

#!/usr/bin/perl

use strict; use warnings;
use List::Util qw( sum );
use Algorithm::Combinatorics qw( combinations );

my @x = (1 .. 10);
my $target_sum = 12;

{
    use integer;
    for my $n ( 1 .. @x ) {
        my $iter = combinations(\@x, $n);
        while ( my $set = $iter->next ) {
            print "@$set\n" if $target_sum == sum @$set;
        }
    }
}

数字会相当迅速地增长：遍历一个40个元素集合的所有子集需要数千天。因此，您应该决定子集的有趣大小。

- Sinan Ünür

1

这种方法的问题在于当总和变得太大时，它没有任何方式进行短路。我的算法可以在Core2 Duo E6750上的不到一秒钟内执行Solve(44, [1 .. 40])（一个40元素集合）。 - cjm

1

你可以使用Data::PowerSet模块，它可以生成一个元素列表的所有子集：

- codaddict

谢谢，这很有帮助，但是有点过于蛮力了。我的集合比较小，但不是那么小，幂集通常也不会太小。我认为我需要做一些递归，当所有可能的未来总和都将变得太大时停止。 - itzy

1

大致算法如下：

有一个“solve”函数，它接受一个已包含数字的列表和一个尚未包含数字的列表。

此函数将循环遍历所有尚未包含的数字。
如果添加该数字会达到目标，则记录该数字集并继续，
如果小于目标，则使用正在查看的数字修改包含/排除列表递归调用该函数。
否则，只需进入循环中的下一步（因为如果您超过了目标，除非允许负数，否则没有添加更多数字的意义）
最初使用空的包含列表和尚未包含数字的完整数字列表调用此函数。

您可以对此进行优化，例如传递总和而不是每次重新计算。此外，如果您最初对列表进行排序，则可以根据以下事实进行基于优化：如果在列表中添加数字k使您超过目标，则添加k + 1也会使您超过目标。

希望这能给您一个足够好的开端。我的Perl非常生疏。

基本上，这是一个暴力算法，其中包含一些快捷方式，因此效率永远不会太高。

- Chris

0

有人之前发布了一个类似的问题，另一个人展示了一个巧妙的shell技巧来回答它。这里有一个shell技巧，但我不认为它像我之前看到的那个解决方案一样好（所以我不会为这种方法负责）。它很聪明，因为它利用了shell扩展：

for i in 0{,+2}{,+3}{,+4}{,+7}; do
  y=$(( $i )); # evaluate expression
  if [ $y -eq 7 ]; then
    echo $i = $y;
  fi;
done

输出：

0+7 = 7
0+3+4 = 7

- PP.

0

这是一个“帮我做作业”的问题吗？

要以确定性的方式完成这个任务需要一个阶乘为N！的算法（即（N-0）*（N-1）*（N-2）...），对于大量输入集合来说速度会非常慢。但是该算法非常简单：计算出集合中每个可能的输入序列，并尝试将序列中的输入相加。如果在任何时候总和匹配，则找到了其中一个答案，保存结果并继续下一个序列。如果在任何时候总和大于目标值，则放弃当前序列并移动到下一个。

您可以通过删除任何大于目标值的输入来稍微优化此过程。另一种优化方法是取序列中的第一个输入I，并创建一个新序列S1，从目标T中减去I以获得新目标T1，然后检查T是否存在于S1中，如果存在则找到了匹配项，否则重复使用S1和T1进行该过程。然而，其顺序仍然是N！。

如果您需要处理非常大的数字集合，则建议您阅读关于遗传算法的相关资料。

C.

- symcbean

这不是一个作业问题，而是一个真实的实际问题。我从事金融研究，不太擅长编程。但我想说话容易做起来难，所以我可能在撒谎。 - itzy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cjm · Accepted Answer

sub Solve
{
  my ($goal, $elements) = @_;

  # For extra speed, you can remove this next line
  # if @$elements is guaranteed to be already sorted:
  $elements = [ sort { $a <=> $b } @$elements ];

  my (@results, $RecursiveSolve, $nextValue);

  $RecursiveSolve = sub {
    my ($currentGoal, $included, $index) = @_;

    for ( ; $index < @$elements; ++$index) {
      $nextValue = $elements->[$index];
      # Since elements are sorted, there's no point in trying a
      # non-final element unless it's less than goal/2:
      if ($currentGoal > 2 * $nextValue) {
        $RecursiveSolve->($currentGoal - $nextValue,
                          [ @$included, $nextValue ],
                          $index + 1);
      } else {
        push @results, [ @$included, $nextValue ]
            if $currentGoal == $nextValue;
        return if $nextValue >= $currentGoal;
      }
    } # end for
  }; # end $RecursiveSolve

  $RecursiveSolve->($goal, [], 0);
  undef $RecursiveSolve; # Avoid memory leak from circular reference
  return @results;
} # end Solve


my @results = Solve(7, [2,3,4,7]);
print "@$_\n" for @results;

这开始是你链接的问题中C#版本的直接翻译，但我稍微简化了一下（现在更加简化了），并删除了一些不必要的变量分配，基于元素列表进行了一些优化，并重新排列条件以使其稍微更有效率。

我现在还添加了另一个重要的优化。当考虑是否尝试使用不能完成总和的元素时，如果该元素大于或等于当前目标的一半，则没有意义。（我们添加的下一个数字将更大。）根据您尝试的集合，这可以更快地终止。（您也可以尝试添加下一个元素而不是乘以2，但然后您必须担心是否会超出列表的末尾。）