perl - 子集求和程序 (Perl)

Question

下面的代码是一个试图解决众所周知的子集和问题的算法。有人给了我这段代码，我对其进行了一些调整和调整，以便它可以在 Perl 中正常运行（上面的代码将运行）。这里，“a”是一组整数，“b”是总和，程序尝试找到“a”的一个子集，该子集和“b”相加，然后在最后打印结果。但是，当“a”的索引（集合中的整数个数）相对较大（大约 200）时，程序无法打印“a”的所有子集，这些子集总和为“b”。我知道这一点是因为我故意选择了一个子集“a”，它总和为我也选择的整数“b”。该程序无法打印“a”的任何子集（虽然很明显至少存在一个）。相信这是某种溢出，我尝试了输出文件目录，然后再次检查文件，我什么也没找到。有任何想法吗？

---

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

  # For extra speed, you can remove this next line

  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(b, [a]
);
print "@$_\n" for @results;

举个例子，我访问了random.org并生成了一组从 1 到 2000 的 200 个随机整数的“a”，取了 200 个随机整数中的 4 个，并创建了一个总和“b”。然后代码如下所示：

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

  # For extra speed, you can remove this next line

  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(4022, [34, 63, 83, 86, 88, 90, 95, 105, 107, 115, 120, 132, 140, 145, 146, 149, 154, 165, 167, 173, 175, 197, 199, 250, 267, 289, 291, 306, 328, 341, 344, 347, 349, 355, 370, 379, 389, 390, 393, 409, 430, 454, 474, 475, 476, 483, 488, 518, 522, 544, 554, 571, 582, 587, 591, 606, 614, 615, 639, 647, 663, 673, 679, 703, 742, 754, 765, 791, 803, 816, 819, 829, 841, 848, 852, 858, 861, 865, 870, 872, 873, 903, 909, 914, 915, 918, 931, 934, 937, 947, 970, 974, 983, 986, 1008, 1013, 1018, 1019, 1071, 1074, 1093, 1095, 1097, 1101, 1104, 1115, 1118, 1122, 1143, 1154, 1163, 1165, 1166, 1173, 1174, 1175, 1177, 1182, 1188, 1192, 1195, 1196, 1248, 1259, 1270, 1277, 1285, 1296, 1306, 1312, 1314, 1317, 1319, 1325, 1326, 1333, 1341, 1346, 1355, 1372, 1393, 1394, 1402, 1404, 1407, 1412, 1425, 1426, 1432, 1433, 1436, 1437, 1452, 1454, 1489, 1498, 1504, 1505, 1515, 1521, 1525, 1542, 1556, 1569, 1591, 1592, 1599, 1622, 1624, 1658, 1680, 1685, 1686, 1696, 1725, 1738, 1757, 1768, 1776, 1781, 1782, 1807, 1815, 1820, 1853, 1866, 1868, 1882, 1888, 1891, 1895, 1909, 1911, 1924, 1942, 1946, 1975, 1983, 1988, 1997]
);
print "@$_\n" for @results;

有一个明显的“a”子集，其总和为“b = 4022”：[389, 1071, 1248, 1314]，但是运行代码（使用已经固定的集合“a”）不会在命令行上打印任何内容，也不输出文件中的任何内容。同样，这可能是一个内存问题，我只是不确定如何解决它。

标签： perlsubset