Задача рюкзака

Введение

Задача рюкзака — это оптимизационная задача, в которой нужно определить, какие предметы положить в рюкзак (ранец) ограниченной вместимости, чтобы максимизировать суммарную стоимость. Предметы могут быть как целыми, так и дробными. В этой главе мы рассматриваем только целочисленный вариант (0/1 knapsack), поскольку дробный вариант решается жадно.

Постановка:
Дано $N$ предметов, каждый имеет вес и стоимость, и рюкзак вместимостью $W$ ($W > 0$). Нужно выбрать некоторые предметы так, чтобы их суммарный вес не превышал $W$, а суммарная стоимость была максимальной. Предметы нельзя делить на части.

Пример: при $W = 5$, $N = 3$ и предметах
$a_1 = (1, 4)$, $a_2 = (2, 5)$, $a_3 = (3, 1)$
(первое число — стоимость, второе — вес)
можно получить максимальную стоимость $4$, положив в рюкзак $a_1$ и $a_3$ (вес $4 + 1 = 5$).

---

Алгоритм

Для решения и отслеживания максимальной стоимости будем вести двумерный массив dp, где:

• dp[i][w] — максимальная стоимость, которую можно получить, используя первые $i$ предметов при ограничении веса $w$.

То есть состояние — это пара $(i, w)$:

• строка i означает, что рассматриваем предметы $1 \ldots i$;
• столбец w — текущий лимит по весу.

Базовые случаи

• Для любого $w$: dp[0][w] = 0, так как предметов нет.
• Для любого $i$: dp[i][0] = 0, так как вес рюкзака равен нулю.

Переход

Рассматриваем предмет $i$ (индексация с 1), у него:

• стоимость value[i-1],
• вес weight[i-1].

На весе w есть два варианта:

1. Не брать предмет $i$: тогда dp[i][w] = dp[i - 1][w].
2. Взять предмет $i$ (если weight[i - 1] <= w): тогда
   dp[i][w] = value[i - 1] + dp[i - 1][w - weight[i - 1]].

Берём максимум из этих вариантов.

---

Реализация

int knapsack(const vector<int>& weights, const vector<int>& values, int capacity) {
    int n = (int)weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w]; // не берем предмет i

            if (weights[i - 1] <= w) { // берем предмет i
                dp[i][w] = max(dp[i][w],
                               values[i - 1] + dp[i - 1][w - weights[i - 1]]);
            }
        }
    }

    return dp[n][capacity];
}