Алгоритм поиска подмножества в двух наборах целых чисел, чьи суммы совпадают

Question

Я ищу алгоритм, который может принимать два набора целых чисел (как положительных, так и отрицательных) и находить в каждом из них подмножества с одинаковой суммой.

Эта проблема аналогична проблеме суммы подмножеств , за исключением того, что я ищу подмножества с обеих сторон.

Вот пример:

Список А {4, 5, 9, 10, 1}

Список B {21, 7, -4, 180}

Так что единственное совпадение здесь: {10, 1, 4, 9} <=> {21, 7, -4}

Кто-нибудь знает, существуют ли алгоритмы для решения подобных проблем?

Пока что единственное решение, которое у меня есть, - это метод грубой силы, который пробует каждую комбинацию, но она выполняется в экспоненциальном времени, и мне пришлось жестко ограничить количество элементов, которые необходимо учитывать, чтобы избежать слишком длительного .

Единственное другое решение, которое я могу придумать, - это запустить факториал в обоих списках и искать там равенства, но это все еще не очень эффективно и экспоненциально дольше по мере увеличения списков.

Answer 1

Как и проблема суммы подмножеств, эта задача является слабо NP-полной, поэтому она имеет решение, которое выполняется во временном полиноме (M), где M - сумма всех чисел, появляющихся в экземпляре задачи , Вы можете достичь этого с помощью динамического программирования. Для каждого набора вы можете сгенерировать все возможные суммы, заполнив 2-мерную двоичную таблицу, где «истина» в (k, m) означает, что сумма m подмножества может быть достигнута путем выбора некоторых элементов из первых k элементов набора.

Вы заполняете его итеративно - вы устанавливаете (k, m) в «true», если (k-1, m) установлено в «true» (очевидно, если вы можете получить m из k-1 элементов, вы можете получить это из k элементов, не выбирая k-й) или если (k-1, md) установлено в «true», где d является значением k-го элемента в наборе (случай, когда вы выбираете k-й элемент).

Заполнение таблицы дает вам все возможные суммы в последнем столбце (тот, который представляет весь набор). Сделайте это для обоих наборов и найдите общие суммы. Вы можете отследить фактические подмножества, представляющие решения, изменив процесс, который вы использовали для заполнения таблиц.

Answer 2

То, что сказали другие, правда:

1. Эта проблема является NP-полной. Простое приведение к обычной сумме подмножеств. Вы можете показать это, заметив, что подмножество A суммирует с подмножеством B (не оба пустые), только если непустое подмножество A union (-B) подводит к нулю.

2. Эта проблема слабо NP-полная, так как она полиномиальна в размере чисел , но предположительно будет экспоненциальной в их логарифмах . Это означает, что проблема проще, чем может дать прозвище «NP-complete».

3. Вы должны использовать динамическое программирование.

Так что я помогаю в этом обсуждении? Ну и код (на Perl):

@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
    next unless exists $b{$m};
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}

sub sums {
    my( @a ) = @_;
    my( $a, %a, %b );
    %a = ( 0 => [] );
    while( @a ) {
        %b = %a;
        $a = shift @a;
        for my $m ( keys %a ) {
            $b{$m+$a} = [@{$a{$m}},$a];
        }
    %a = %b;
    }
    return %a;
}

печатает

sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)

Итак, что примечательно, существует более одного решения, которое работает в вашей исходной задаче!

Редактировать : Пользователь Ици правильно указал, что это решение было неправильным, и, что еще хуже, несколькими способами !! Я очень сожалею об этом, и я надеюсь, что рассмотрел эти проблемы в новом коде выше. Тем не менее, есть еще одна проблема, а именно, что для любой конкретной подмножества сумма выводит только одно из возможных решений. В отличие от предыдущих проблем, которые были ошибками, я бы классифицировал это как намеренное ограничение. Желаем удачи и остерегайтесь ошибок!

Answer 3

Большое спасибо за все быстрые ответы!

Решение динамического программирования на самом деле не отличается от исчерпывающего подхода, который у нас есть сейчас, и я думаю, что если нам нужно оптимальное решение, нам нужно рассмотреть каждую возможную комбинацию, но время, необходимое для генерации этого исчерпывающего списка сумм, слишком долго.. Провел быструю проверку, и время, необходимое для генерации всех возможных сумм для x количества элементов, очень быстро превысило 1 минуту:

11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds

, что для бизнес-задачи, которую мы пытаемся решить, не совсем приемлемо .. Я вернусь к чертежной доске и посмотрим, действительно ли нам нужно знать все решения или мы можем сделать только одно ( Наименьшее / наибольшее подмножество, например) вместо этого и, надеюсь, это может помочь просто решить проблему и заставить мой алгоритм работать в ожидании.

Спасибо все равно!

Answer 4

сумма подмножества является Np-полной, и вы можете полиномиально свести к ней свою проблему, поэтому ваша задача также является NP-полной.