15.5. Задача о рюкзаке

Существует много различных вариаций этой задачи. Можно считать, что есть лишь одна копия каждого предмета (версия «без повторений»), а можно — что копий каждого предмета бесконечно много (версия «с повторениями»).

Версия «с повторениями»

Пусть $k[j]$ — максимальная возможная суммарная стоимость при вместимости рюкзака $j$. Начальное состояние: $k[0]=0$. Переход — выбор последнего взятого предмета:

Ответ на задачу: $\max_{0 \leqslant j \leqslant W} k[j]$. Получаем решение за $O(nW)$ с $O(W)$ дополнительной памяти.

1
2
3
4
5
6
7
8
9

def knapsack_unbounded(W: int, weights: list[int], prices: list[int]) -> int:
    """Рюкзак с повторениями. Возвращает максимальную стоимость."""
    n = len(weights)
    k = [0] * (W + 1)
    for j in range(W + 1):
        for i in range(n):
            if weights[i] <= j:
                k[j] = max(k[j], k[j - weights[i]] + prices[i])
    return k[W]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
#include <algorithm>
using namespace std;

// Рюкзак с повторениями
int knapsackUnbounded(int W, vector<int>& w, vector<int>& p) {
    int n = w.size();
    vector<int> k(W + 1, 0);
    for (int j = 0; j <= W; j++)
        for (int i = 0; i < n; i++)
            if (w[i] <= j)
                k[j] = max(k[j], k[j - w[i]] + p[i]);
    return k[W];
}

Версия «без повторений»

Для того, чтобы не взять один предмет несколько раз, введём дополнительный параметр. Пусть $k[i, j]$ — максимальная возможная суммарная стоимость, если разрешается брать только предметы с номерами не больше $i$, а рюкзак имеет вместимость $j$. Начальные состояния: $k[0, j] = k[i, 0] = 0$. Переход: либо $i$-й предмет входит в ответ, либо нет.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def knapsack_01(W: int, weights: list[int], prices: list[int]) -> int:
    """Рюкзак без повторений, O(nW) памяти."""
    n = len(weights)
    k = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            k[i][j] = k[i-1][j]
            if weights[i-1] <= j:
                k[i][j] = max(k[i][j], k[i-1][j - weights[i-1]] + prices[i-1])
    return k[n][W]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int knapsack01(int W, vector<int>& w, vector<int>& p) {
    int n = w.size();
    vector<vector<int>> k(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= W; j++) {
            k[i][j] = k[i-1][j];
            if (w[i-1] <= j)
                k[i][j] = max(k[i][j], k[i-1][j - w[i-1]] + p[i-1]);
        }
    return k[n][W];
}

Оптимизация памяти

При вычислении $k[i, j]$ нужны только значения $k[i-1, q]$ с $q \leqslant j$. Если перебирать $j$ в порядке убывания, можно обойтись одномерным массивом: при обработке состояния $(i, j)$ в $k[0..j]$ хранятся значения $k[i-1, 0], \ldots, k[i-1, j]$, а в $k[j+1..W]$ — значения $k[i, j+1], \ldots, k[i, W]$.

1
2
3
4
5
6
7
8

def knapsack_01_opt(W: int, weights: list[int], prices: list[int]) -> int:
    """Рюкзак без повторений, O(W) памяти."""
    n = len(weights)
    k = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):  # убывание!
            k[j] = max(k[j], k[j - weights[i]] + prices[i])
    return k[W]

1
2
3
4
5
6
7
8

int knapsack01Opt(int W, vector<int>& w, vector<int>& p) {
    int n = w.size();
    vector<int> k(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = W; j >= w[i]; j--)  // убывание!
            k[j] = max(k[j], k[j - w[i]] + p[i]);
    return k[W];
}