Рюкзак и состояние подпоследовательности

Рюкзак показывает, как один дополнительный параметр — доступная вместимость — меняет одномерный DP. Каждый предмет можно взять не больше одного раза.

Как уложить ценные предметы в один рюкзак

Есть предметы с весами и ценностями; вместимость W. Максимизировать сумму ценностей без превышения веса. Для весов [2,3,4], ценностей [4,5,10], W=6 ответ 14: взять предметы весов 2 и 4.

Что проверяют все наборы предметов

Для каждого предмета попробовать «взять» и «не взять», проверяя вес. Это до 2^n подмножеств. Многие разные подмножества приводят к одинаковой паре «сколько предметов обработано, сколько места осталось».

Почему одинаковый остаток вместимости повторяется

Нельзя описать будущее только индексом предмета: два набора с разным весом имеют разные возможности. Однако полный список выбранных предметов тоже не нужен; достаточно лучшей ценности для каждой вместимости.

Как выбор предмета меняет доступную ёмкость

После обработки некоторого префикса предметов dp[w] — максимальная ценность при допустимом общем весе не больше w. Когда добавляем предмет (weight, value), для w >= weight сравниваем:

• не брать: прежнее dp[w];
• взять: dp[w-weight] + value из состояния до текущего предмета.

Чтобы dp[w-weight] ещё относилось к прежнему префиксу, обход w обязан идти от W вниз к weight.

Что означает лучшая ценность при данном весе

После обработки первых i предметов dp[w] равен оптимуму среди подмножеств только этих i предметов с весом не больше w. Обратный обход гарантирует, что текущий предмет не попадёт в dp[w-weight] второй раз.

Почему вместимость надо обходить справа налево

1. Заполнить dp[0..W] нулями.
2. Для каждого предмета проверить входные длины и положительность веса.
3. Идти по w от W вниз до weight.
4. Обновить dp[w] = max(dp[w], dp[w-weight] + value).
5. Вернуть dp[W].

Как не взять один предмет дважды

Вес 0 здесь запрещён, чтобы не скрывать особую обработку. Один массив корректен именно из-за обратного направления цикла.

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

int knapsack01(const vector<int>& weights, const vector<int>& values, int capacity) {
    if (weights.size() != values.size() || capacity < 0) {
        throw invalid_argument("invalid knapsack input");
    }

    vector<int> dp(capacity + 1, 0);
    for (size_t item = 0; item < weights.size(); ++item) {
        int weight = weights[item];
        int value = values[item];
        if (weight <= 0) throw invalid_argument("weight must be positive");

        for (int current = capacity; current >= weight; --current) {
            dp[current] = max(dp[current], dp[current - weight] + value);
        }
    }
    return dp[capacity];
}

int main() {
    assert(knapsack01({2, 3, 4}, {4, 5, 10}, 6) == 14);
    assert(knapsack01({5}, {8}, 4) == 0);
    cout << knapsack01({1, 3, 4}, {15, 20, 30}, 4) << '\n';
}

Python 3

def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    if len(weights) != len(values) or capacity < 0:
        raise ValueError("invalid knapsack input")

    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        if weight <= 0:
            raise ValueError("weight must be positive")
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]


assert knapsack_01([2, 3, 4], [4, 5, 10], 6) == 14
assert knapsack_01([5], [8], 4) == 0
print(knapsack_01([1, 3, 4], [15, 20, 30], 4))

Во что обходится таблица рюкзака

Время O(nW), память O(W). Это псевдополиномиальный алгоритм: при W=10^9 он непригоден, даже если предметов мало. Предполагаются целые неотрицательные ценности и положительные целые веса; отрицательные ценности обычно просто не берут, но условия могут требовать иное.

Где нулевой вес меняет переход

W=0 даёт 0. Предмет тяжелее рюкзака пропускается. Одинаковые веса — отдельные предметы, но каждый берётся максимум раз. Нулевой вес требует явного решения, потому что обратный обход не защищает от неоднозначности его обработки. Ошибка обхода снизу вверх превращает задачу в неограниченный рюкзак.

Какие рюкзаки проверяют однократный выбор

• вместимость 0;
• предмет тяжелее вместимости;
• один предмет, который помещается и не помещается;
• [2,3,4], [4,5,10], 6 -> 14;
• вес 2, ценность 3, W=4: ответ должен быть 3, а не 6 в версии 0/1.

Когда нужен параметр оставшейся ёмкости

Сигналы: «каждый объект взять или пропустить», «ограниченный бюджет/вес/время», «максимум ценности» и сравнительно небольшой целочисленный лимит. Если выбор меняет доступный ресурс, включите этот ресурс в состояние.

Когда предметы можно брать многократно

При W слишком большом нужна другая ось DP, meet-in-the-middle или приближённый алгоритм. Если предметы можно брать неограниченно, направление цикла должно быть прямым. Если нужен точный вес, а не «не больше», иначе задаются базы и недостижимые состояния.

Самопроверка направления внутреннего цикла

Вопрос: почему цикл по current идёт вниз?
Ответ: dp[current-weight] должен быть ответом до обработки текущего предмета. Прямой цикл уже увидит обновлённое значение и позволит взять этот же предмет повторно.

Самопроверка значения без выбора

Вопрос: что вернёт 0/1-версия для одного предмета веса 2 и ценности 3 при W=4?
Ответ: 3. Предмет нельзя дублировать, хотя места достаточно для двух копий.

Потренируйте состояние рюкзака

Измените условие: каждый тип монеты можно брать сколько угодно. Оставьте состояние dp[amount], но поменяйте направление обхода суммы. Проверьте, почему для монеты 2 и суммы 4 теперь допустим ответ из двух монет.

Самостоятельный рюкзак без раскрытия ответа

До кода определите, можно ли повторно выбирать предмет, и обоснуйте направление обхода ёмкости.

Задача 1

Есть проекты с затратой времени и пользой, а также лимит времени. Каждый проект можно взять не более одного раза. Верните максимальную пользу и один набор индексов проектов.

Что защищает от двойного использования предмета

В рюкзаке состояние отвечает не «что я выбрал», а «лучший результат при данном ресурсе». Направление обхода — часть доказательства, а не техническая деталь.