Найти наименьшую сумму подмножества, соответствующую другой сумме подмножеств

Question

У меня есть реальная проблема (не домашняя работа!), Которая требует найти сумму подмножества множества A, равную сумме подмножества некоторого другого набора B.

Очень похожий вопрос с полезным ответом здесь .

Рассмотрим этот пример:

@a = qw(200 2000 2000 2000 4000);
@b = qw(528 565 800 1435 2000 2000 2872);

Используя код , указанный в принятом ответе на этот вопрос, я получаю следующий вывод:

sum(200 2000 4000) = sum(528 800 2000 2872)
sum(200 4000 4000) = sum(528 800 2000 2000 2872)
sum(200 4000) = sum(528 800 2872)
sum(200 2000 2000 2000 4000) = sum(528 800 2000 2000 2000 2872)

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

sum(200 4000) = sum(528 800 2872)

потому что все остальные ответы также имеют 200 и 4000 в сумме. То есть я ищу только самые «простые» возможные суммы (в том смысле, что они используют наименьшее количество элементов). Может кто-нибудь предложить достаточно эффективный способ сделать это? (С грубой силой все в порядке, так как мои массивы не такие большие.)

Кроме того, я должен отметить, что вторая строка вывода, sum(200 4000 4000) ..., неверна, потому что 4000 появляется только один раз в @a. Боюсь, я недостаточно хорошо понимаю алгоритм, чтобы понять, почему это происходит.

Любая помощь с любым из них будет высоко ценится!

Answer 1

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

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

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

Вот код Python, который генерирует все возможные значения, в которых они могут пересекаться:

    def gen_sum(a):
        r = { 0: [] }
        for x in a:
            for y, v in r.items():
                if not (x+y) in r or len(r[x+y]) > len(v) + 1:
                    r[x+y] = v + [x]
        return r

    def gen_sums(a, b):
        asum = gen_sum(a)
        bsum = gen_sum(b)
        return [ (k, v, bsum[k]) for k,v in asum.items() if k in bsum ][1:]

Запустив его на ваших образцах данных, я получил:

[(4000, [4000], [2000, 2000]), (6000, [2000, 4000], [565, 1435, 2000, 2000]), (2000, [2000], [2000]), (4200, [200, 4000], [528, 800, 2872]), (10200, [200, 2000, 2000, 2000, 4000], [528, 565, 800, 1435, 2000, 2000, 2872]), (8200, [200, 2000, 2000, 4000], [528, 800, 2000, 2000, 2872]), (6200, [200, 2000, 4000], [528, 800, 2000, 2872])]

РЕДАКТИРОВАТЬ: Исправлена ​​опечатка, а также только что заметил, что святые дерьмо тонны людей уже ответили на это очень быстро.

Answer 2

Вам нужно изменить отношение повторения, а не только вывод.Рассмотрим {1,2,20,23,42} и {45}.Исходный алгоритм выведет {1,2,42}, {45} вместо {20,23}, {45}.Это связано с тем, что значение 42 считается последним, а когда оно суммируется с 45, оно будет перезаписывать значение сегмента 45, ранее содержащее {20,23}

Вместо сохранения [set, sum] для каждого значения, вам нужносохранить [минимальный набор, сумма], а затем взять минимумы в конце.

Мой Perl ужасен, но что-то вроде этого

$a{$m+$a} = [min-length(@{$a{$m}},$a{$m+$a}[0]),$a];

, где min-length возвращает меньший набор

Answer 3

Вот обновленный алгоритм, который дает все суммы:

my @a = qw(200 2000 2000 2000 4000);
my @b = qw(528 565 800 1435 2000 2000 2872);

my %a = sums( @a );
my %b = sums( @b );

for my $m ( keys %a ) {
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n" if exists $b{$m};
}

sub sums {
    my( @a ) = @_;

    return () unless @a;

    my %a;

    while( @a ) {
        $a = shift @a;

        for my $m ( keys %a ) {
            $a{$m+$a} = [@{$a{$m}},$a];
        }

        $a{$a} = [$a];
    }

    return %a;
}

Все, что вам нужно сделать, это найти самый короткий (ые), но другие уже рассмотрели это:)

НТН,

Пол

Answer 4

Я не очень хорош с Perl. Но,

for $m ( keys %a ) {
print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n" if exists $b{$m};

}

Измените эту строку, чтобы подсчитать количество элементов в наборе $ a и $ b для каждого $ m. Когда вы закончите цикл по всем из них, выберите один с наименьшим количеством элементов.