Учитывая массив, вы должны найти максимально возможную две равные суммы

Ответ 1

Рекомендуемый подход

Я предлагаю решить это с помощью DP, где вместо отслеживания A, B (размер двух наборов) вы вместо этого отслеживаете A + B, AB (сумма и разность двух наборов).

Затем для каждого элемента массива попробуйте добавить его к A или B или никому.

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

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

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

Пример кода Python

from collections import defaultdict

def max_equal_sum(E):
    D=defaultdict(int)            # Map from abs difference to largest sum
    D[0]=0                        # Start with a sum and difference of 0
    for a in E:                   # Iterate over each element in the array
        D2=D.copy()               # Can keep current sum and diff if element is skipped
        for d,s in D.items():     # d is difference, s is sum
            s2 = s+a              # s2 is new sum
            for d2 in [d-a,d+a]:  # d2 is new difference
                D2[abs(d2)] = max(D2[abs(d2)],s2) # Update with largest sum
        D=D2
    return D[0]/2                 # Answer is half the sum of A+B for a difference of 0

print max_equal_sum([1,2,3,4,6])  # Prints 8
print max_equal_sum([4,10,18,22]) # Prints 22

Ответ 2

Самый большой набор со значениями от 0 до 1000, который не имеет двух подмножеств с равной суммой, имеет 9 элементов, например:

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512}

Если вы добавите десятый элемент, то он будет равен сумме подмножества девяти предыдущих значений.

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

Сумма исключенных элементов в диапазоне от 0 до 1000. Создание сита для проверки того, какие значения в этом диапазоне могут быть сформированы с элементами в наборе, займет не более 50 × 1000 шагов. (Мы можем сохранить минимальное количество значений, которые суммируются до каждой суммы, а не логические, и использовать их для включения только сумм, которые могут быть сделаны с 9 или менее элементами.)

Если мы затем посмотрим на суммы исключенных чисел от малого до большого, это означает просмотр сумм включенных чисел от большого к маленькому. Для каждой суммы исключенных значений мы проверяем, какие (до 9) элементы могут сформировать эту сумму (очевидно, не тривиальный шаг, но мы знаем, что количество элементов находится между минимальным значением, сохраненным в сите, и 9), и это дает нам набор исключенных, а также набор включенных чисел. Затем мы используем аналогичную ситовую технику, чтобы проверить, могут ли включенные числа сформировать половину суммы; это будет в диапазоне от 1 до 500 и займет не более 50 × 500 шагов.

При этом, конечно, нечетная/четность должна учитывать: если общая сумма нечетна, необходимо исключить подмножество с нечетной суммой; если общая сумма четная, следует исключить только подмножества с четной суммой.

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

Вот некоторые из частей в действии. Во-первых, сито, чтобы найти суммы наборов до 9 значений, которые могут быть исключены (и имеют правильную нечетную/четность), проверенные с 20 значениями с суммой 999:

function excludedSums(values) {
    var sieve = [0];
    for (var i in values) {
        var temp = [];
        for (var j in sieve) {
            if (sieve[j] == 9) continue;
            var val = values[i] + Number(j);
            if (!sieve[val] || sieve[j] + 1 < sieve[val]) {
                temp[val] = sieve[j] + 1;
            }
        }
        for (var j in temp) {
            sieve[j] = temp[j];
        }
    }
    var odd = values.reduce(function(ac, el) {return ac + el}, 0) % 2;
    for (var i in sieve) {
        if (Number(i) % 2 != odd) delete sieve[i];
    }
    return sieve;
}
var set = [40,7,112,15,96,25,49,49,31,87,39,8,79,40,73,49,63,55,12,70];
var result = excludedSums(set);
for (var i in result) document.write(i + ", ");