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

Задача о рюкзаке (0/1): даны предметы с весом и ценностью; нужно набрать максимальную суммарную ценность, не превысив вместимость W. Каждый предмет берётся целиком или не берётся вовсе. Решается динамическим программированием по весу.

Сложность: время O(n · W), память O(W) при оптимизации до одной строки таблицы. Это псевдополиномиальная сложность — она зависит от величины W, а не только от числа предметов.

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for c in range(W, wt - 1, -1):
            dp[c] = max(dp[c], dp[c - wt] + val)
    return dp[W]

print(knapsack([1, 3, 4], [15, 20, 30], 4))  # 35