Knapsack Problems
0/1 Knapsack — O(nW) time, O(nW) space
Each item used at most once. dp[i][w] = max value using first i items with capacity w.
def knapsack_01(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])
[Description truncada. Veja o README completo no GitHub.]