Даны n предметов с весом и ценностью и рюкзак вместимостью W. Каждый предмет берём не более одного раза, максимизируя суммарную ценность и не превышая W. Жадность по ценности на вес здесь не работает (пример со 160 и 220 из урока о жадных алгоритмах), поэтому используем ДП.

Состояние, переход, база, ответ

  • Состояние: dp[i][w] — лучшая ценность при использовании первых i предметов и вместимости w.
  • Переход: предмет i пропускаем (dp[i-1][w]) или берём (dp[i-1][w-weight] + value, если weight <= w) и оставляем максимум.
  • База: dp[0][w] = 0.
  • Ответ: dp[n][W].
Таблица рюкзака для четырёх предметов и вместимости 7
Таблица рюкзака для четырёх предметов и вместимости 7

Таблица в коде

python
def knapsack(items, cap):
    n = len(items)
    # dp[i][w]: best value using the first i items with capacity w
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                       # skip item i
            if weight <= w:                               # or take it
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)
    return dp