Равной суммы подмножеств гибридной

Question

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

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

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

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

Answer 1

Нет проблем, вот решение 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 
} 

Answer 2

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

Самое сложное дело, вероятно, когда п около 30.

Answer 3

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

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

Answer 4

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

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