DSA Knapsack Problem
Learn how the 0/1 knapsack problem is solved with dynamic programming, from the naive exponential recursion to a space-optimized table.
The 0/1 Knapsack Problem
Given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, the 0/1 knapsack problem asks which items to take to maximize total value without exceeding the capacity. The "0/1" means each item is either taken whole or left behind entirely — it cannot be split, which is exactly what makes greedy strategies fail here.
- Each item can be used at most once (0 or 1 times)
- Items cannot be split into fractions, unlike the fractional knapsack problem
- The goal is to maximize total value subject to a total weight limit
- A brute-force solution checking every subset takes O(2^n) time
Why Greedy Fails Here
You might try taking items in order of best value-to-weight ratio, as in fractional knapsack. But because items can't be split, the highest-ratio item might use up capacity in a way that blocks a better combination of the remaining items. Dynamic programming instead considers, for every item, both possibilities — include it or exclude it — and reuses previously computed answers instead of rechecking every subset.
Example
def knapsack_recursive(weights, values, capacity, n):
if n == 0 or capacity == 0:
return 0
if weights[n - 1] > capacity:
return knapsack_recursive(weights, values, capacity, n - 1)
exclude = knapsack_recursive(weights, values, capacity, n - 1)
include = values[n - 1] + knapsack_recursive(
weights, values, capacity - weights[n - 1], n - 1
)
return max(include, exclude)
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_recursive(weights, values, 5, len(weights))) # 7The DP Table Solution
The standard DP solution builds a table where table[i][w] holds the best value achievable using the first i items with capacity w. Each cell is filled using the answer for one fewer item, either excluding the current item or including it and reducing the remaining capacity by its weight.
Example
def knapsack_dp(weights, values, capacity):
n = len(weights)
table = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] > w:
table[i][w] = table[i - 1][w]
else:
exclude = table[i - 1][w]
include = values[i - 1] + table[i - 1][w - weights[i - 1]]
table[i][w] = max(include, exclude)
return table[n][capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_dp(weights, values, 5)) # 7Example
def knapsack_optimized(weights, values, capacity):
table = [0] * (capacity + 1)
for i in range(len(weights)):
# Iterate weight backward so each item is only used once.
for w in range(capacity, weights[i] - 1, -1):
table[w] = max(table[w], values[i] + table[w - weights[i]])
return table[capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_optimized(weights, values, 5)) # 7Exercise: DSA Knapsack Problem
What is the main constraint in the 0/1 knapsack problem?
