Программа подмножества сумм (Perl) - PullRequest
Новая
       8

Программа подмножества сумм (Perl)

0 голосов
/ 13 января 2019

Код ниже представляет собой алгоритм, который пытается решить хорошо известную проблему суммы подмножеств. Кто-то дал мне этот код, я сделал несколько настроек и поправок, чтобы он правильно работал в Perl (приведенный выше код будет работать). Здесь «a» - это набор целых чисел, а «b» - сумма, и программа пытается найти подмножество «a», которое суммирует с «b», а затем выводит результат в конце. Однако, когда индекс «a» (количество целых чисел в наборе) относительно велик (около 200), программе не удается вывести все подмножества «a», которые суммируются с «b». Я знаю это, потому что я специально выбрал подмножество «a», которое суммируется с целым числом «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(b, [a]
);
print "@$_\n" for @results;

Чтобы привести пример, я пошел на random.org и сгенерировал набор "a" из 200 случайных целых чисел от 1 до 2000, взял 4 из этих случайных 200 целых чисел и создал сумму "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») ничего не печатает в команде ни строки, ни чего-либо в выходном файле. Опять же, это, вероятно, проблема с памятью, я просто не знаю, как обойти это.

...