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

Эта проблема является 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])]

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

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

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;
}

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

HTH,

Павел

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

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

У меня ужасный perl, но что-то вроде этого

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

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

Я не очень разбираюсь в Perl. Но,

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

}

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