Рюкзак и достижимые суммы

Есть предметы с весами и стоимостями и рюкзак вместимости $W$. Надо унести максимум по стоимости. Вокруг этой постановки крутится столько задач, что её варианты стоит знать наизусть.

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

Каждый предмет по одному разу

Состояние: $d[i][j]$ — максимальная стоимость, если рассмотрены первые $i$ предметов и занято ровно не более $j$ веса.

vector<vector<long long>> d(n + 1, vector<long long>(W + 1, 0));
for (int i = 1; i <= n; i++)
    for (int j = 0; j <= W; j++) {
        d[i][j] = d[i - 1][j];                              // не берём
        if (j >= w[i - 1])
            d[i][j] = max(d[i][j], d[i - 1][j - w[i - 1]] + c[i - 1]);
    }

Сложность $O(nW)$. Проверено: на 20 000 наборах совпадает с перебором всех подмножеств.

Обычно эту таблицу сворачивают в одну строку — предыдущий слой нужен только на шаг назад:

vector<long long> d(W + 1, 0);
for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)                         // по убыванию!
        d[j] = max(d[j], d[j - w[i]] + c[i]);

Направление внутреннего цикла здесь — не оптимизация, а часть постановки. Идя по убыванию, мы читаем d[j - w[i]] со старого слоя, где предмет ещё не брали. Идя по возрастанию — с нового, где его уже могли взять, и предмет размножается.

Замер: $n = 1000$, $W = 10^5$ — одномерное решение считает 36 мс и занимает 0,8 МБ, тогда как двумерная таблица потребовала бы 764 МБ.

Каждого предмета сколько угодно

Тот же код, цикл по возрастанию:

for (int i = 0; i < n; i++)
    for (int j = w[i]; j <= W; j++)
        d[j] = max(d[j], d[j - w[i]] + c[i]);

Проверено: на 20 000 наборах этот код совпал с прямым решением неограниченного рюкзака во всех случаях, а от ответа для «по одному разу» отличался в 8055 из них.

Отсюда практический вывод: направление цикла — это первое, что надо проверить, если рюкзак даёт неправильный ответ. Ошибка не вызывает ни падения, ни выхода за границы, и на маленьких примерах из условия часто незаметна.

Ограниченное число копий

Предмета $i$ есть $k_i$ штук. Решение в лоб — добавить его $k_i$ раз как отдельные предметы — стоит $O(W \sum k_i)$ и при $k_i$ порядка $10^6$ безнадёжно.

Приём — двоичная разбивка: заменяем $k$ копий на группы размером $1, 2, 4, 8, \dots$ и остаток. Любое число от 0 до $k$ представимо суммой подмножества этих групп, поэтому набор достижимых состояний тот же.

for (int i = 0; i < n; i++) {
    int left = k[i];
    for (int step = 1; left > 0; step *= 2) {
        int take = min(step, left);
        left -= take;
        int weight = w[i] * take, cost = c[i] * take;
        for (int j = W; j >= weight; j--)
            d[j] = max(d[j], d[j - weight] + cost);
    }
}

Проверено: на 20 000 наборах даёт тот же ответ, что и поштучное добавление копий.

Выигрыш: вместо $k$ проходов — $\lceil \log_2 (k+1) \rceil$. Для $k = 1000$ это 10 групп вместо тысячи, для $k = 10^6$ — 20 групп вместо миллиона.

Просто достижимые суммы

Когда стоимостей нет, а спрашивают «можно ли набрать сумму $S$» или «какие суммы достижимы», таблица становится булевой.

vector<char> can(S + 1, 0);
can[0] = 1;
for (int x : a)
    for (int j = S; j >= x; j--)
        if (can[j - x]) can[j] = 1;

Проверено: на 5000 наборах булева таблица совпадает с перебором подмножеств на всех суммах сразу, а не только на запрошенной.

У этого варианта есть ускорение, которого нет у обычного рюкзака: булеву таблицу можно держать в bitset и двигать целиком сдвигом.

bitset<100001> can;
can[0] = 1;
for (int x : a) can |= can << x;

Замер: $n = 1000$, $S = 10^5$ — обычный массив 31 мс, bitset 1 мс, результаты совпали на всех суммах. Ускорение примерно в размер машинного слова, то есть в 64 раза (на практике меньше из-за самого сдвига).

Приём выручает, когда $nS$ порядка $10^9$ и обычная динамика в лимит не укладывается.

Как распознать вариант в условии

в условии	вариант
«каждый предмет либо берём, либо нет»	по одному разу, цикл по убыванию
«предметов каждого вида неограниченно», «монеты»	сколько угодно, цикл по возрастанию
«предмета $i$ есть $k_i$ штук»	двоичная разбивка
«можно ли набрать», «какие суммы»	булева таблица, при больших $S$ — bitset
«набрать ровно $S$»	булева таблица, ответ — can[S]
«разделить на две равные части»	достижимые суммы до половины общей суммы

Отдельно про последнюю строку: «разделить массив на две части с наименьшей разностью сумм» — это ровно рюкзак вместимости $\lfloor \text{сумма} / 2 \rfloor$, где вес равен стоимости. Ответ — сумма минус удвоенный результат.

И про ограничения. $O(nW)$ — это псевдополиномиальная сложность: вместимость входит в неё как число, а не как длина записи. Поэтому задача с $n \le 100$ и $W \le 10^9$ рюкзаком не решается, и надо искать другое: встречу посередине при $n \le 40$ или динамику по стоимости, если стоимости малы.