Гибрид равных сумм - PullRequest
Новая
       14

Гибрид равных сумм

7 голосов
/ 08 февраля 2009

Проблема заключается в следующем:

Вам дан набор натуральных чисел {a1, a2, a3, ..., an}, в которых нет одинаковых чисел (a1 существует только один раз, a2 существует только один раз, ...), например, A = { 12, 5, 7, 91}. Вопрос: Существуют ли два непересекающихся подмножества A, A1 = {b1, b2, ..., bm} и A2 = {c1, c2, ..., ck}, так что b1 + b2 + ... + bm = c1 + c2 + ... + ck?

Обратите внимание на следующее: А1 и А2 не обязаны покрывать А, поэтому проблема не сводится автоматически к проблеме суммы подмножеств. например, A = {2,5,3,4,8,12} A1 = {2,5}, поэтому сумма A1 равна 7 A2 = {3,4}, поэтому сумма A2 равна 7 Мы нашли два непересекающихся подмножества A с описанным свойством, поэтому проблема решена.

Как я могу решить эту проблему? Могу ли я сделать что-то лучше, чем найти все возможные (непересекающиеся) подмножества, вычислить их суммы и найти две равные суммы?

Спасибо за ваше время.

Ответы [ 4 ]

3 голосов
/ 08 февраля 2009

Нет проблем, вот решение O(1). 

A1 = {}; 
A2 = {};
sum(A1) == sum(A2) /* == 0 */

QED.

Серьезно, одна оптимизация, которую вы можете сделать (предполагая, что мы говорим о положительных числах), состоит в том, чтобы проверять только подмножества меньше или равные sum(A)/2.

Для каждого элемента в A есть три параметра, которые делают его O(3^N):

  1. Поместите это в A1
  2. Поместите это в A2
  3. Откажитесь от него

Вот наивное решение в Perl (которое подсчитывает совпадения, вы можете получить ранний возврат, если вы просто хотите проверить существование). 

use List::Util qw/sum/;

my $max = sum(@ARGV)/2;
my $first = shift(@ARGV); # make sure we don't find the empty set (all joking aside) and that we don't cover same solution twice (since elements are unique)
my $found = find($first,0, @ARGV);
print "Number of matches: $found\n";

sub find {
    my ($a, $b, @tail) = @_;
    my $ret = $a == $b? 1 : 0; # are a and b equal sub-sets?
    return $ret unless @tail;

    my $x = shift @tail;
    $ret += find($a + $x, $b, @tail) if $a + $x <= $max; # put x in a
    $ret += find($a, $b + $x, @tail) if $b + $x <= $max; # put x in b
    return $ret + find($a, $b, @tail); # discard x
}
2 голосов
/ 08 февраля 2009

Если ответ отрицательный, то сумма всех n чисел не менее 2 ^ n-1. Так что, если n большое, а числа, например, являются 32-битными целыми, то ответ почти всегда да. Если n мало, вы можете, вероятно, перебором.

Самый сложный случай, вероятно, когда n около 30.

1 голос
/ 08 февраля 2009

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

Если такие s существуют, это означает, что вы нашли два разных подмножества с одинаковой суммой. Они могут не быть непересекающимися, но тогда вы можете удалить общие элементы из каждого набора и получить два непересекающихся набора с равными суммами. Хотя один из них может быть пустым.

0 голосов
/ 10 февраля 2009

Эта проблема кажется, по крайней мере, такой же сложной, как SUBSET-SUM. Если мы сможем найти два подмножества A: B = {b1, ..., bp} и C = {c1, ..., cq}, такие что b1 + ... + bp = -c1 -...- cq, или если мы определим, что ничего не существует, то мы решили SUBSET-SUM (A) (игнорируя тривиальный случай, когда 0 ∈ A).

Я не уверен, что вы подразумеваете под этим, необязательно, чтобы B и C покрывали A, поэтому проблема не сводится автоматически к проблеме подмножества сумм. Пожалуйста, проверьте определение SUBSET-SUM.

...