Задача динамического программирования в USACO

Question

В разделе 2.2 проблема, называемая «суммой подмножеств», требует, чтобы вы вычислили, каким образом целое множество от 1 до n можно разбить на два множества, суммы которых идентичны.

Я знаю,повторение:

f [i] [j]: число путей, суммирующих до j с 1 ... i

f [i] [j] = f [i-1] [j] + f [i-1] [ji]

, если начальное условие:

f [1] [1] = 1; // все остальные равны нулю, основной цикл начинается с 2

ИЛИ:

f [0] [0] = 1; // все остальные равны нулю,основной цикл начинается с 1

все ответы f [n] [n * (n + 1) / 4]. Значит ли это, что начальное условие не влияет на ответ?

но если я использую одномерный массив, скажем, f [N]:

let f [0] = 1, цикл из 1 (поэтому f [0] равно f [0] [0] вфакт), ответ f [n] / 2

или f [1] = 1, цикл из 2 (f [1] - это f [1] [1]), ответ - f [n]

Я так растерялся ...

Answer 1

Я не знаю, застряли ли вы в этой проблеме, но вот решение для всех, кто сталкивается с этой проблемой.

Позвольте way [i] быть числом способов, которым вы можете получить сумму i, используя подмножество чисел 1 ... N.

Тогда он становится вариантом алгоритма ранца 0-1:

базовый вариант: способы [0] = 1

for (int i = 1; i <= N; i++) {
    for (int j = sum - i; j >= 0; --j) { //sum is n*(n+1)/2
        ways[j + i] += ways[j];
    }
}

Ваш ответ находится в пути [сумма / 2] /2.