Knapsack derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.
Table of Contents
What is Knapsack
The knapsack problem is the following problem in combinatorial optimization:
Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Core idea
- You have n items
- each item has weight wt[i]
- each item has value val[i]
- a bag with capacity W
Goal: maximise total value without exceeding capacity
Knapsack variants
| Variant | Can reuse item? | Typical problems |
|---|---|---|
| 0/1 Knapsack | ❌ No | subset sum, partition (DP) |
| Unbounded Knapsack | ✅ Yes | coin change, rod cutting (DP) |
| Fractional | partial | Greedy Problem (NOT DP) |
0/1 Knapsack
- Each item has only two choices:
- skip the item
- take item once
- No fractions of the item
- No repeats of the item
Eample
weight = [1,3,4,5]
value = [1,4,5,7]
Bag capacity = 7kg.
Which items should be included to have maximum value?
Try all valid combinations (≤ 7 kg)
A → weight 1, value 1
B → weight 3, value 4
C → weight 4, value 5
D → weight 5, value 7
A + B → weight 4, value 5
A + C → weight 5, value 6
A + D → weight 6, value 8
B + C → weight 7, value 9 ✅
B + D → weight 8 ❌ (too heavy)
C + D → weight 9 ❌
A + B + C → weight 8 ❌
A + B + D → weight 9 ❌Fractional Knapsack
Use a greedy approach to solve such a problem. Partial items are allowed in these types of problems
Unbounded Knapsack
We have an unlimited supply of items
0/1 Knapsack
weight = [1,3,4,5]
value = [1,4,5,7]
Bag capacity = 7kg.
Which items should be included to have maximum value?
xxxx
make decison tree here
xxxxxxx
\
Classic Knapsack
Take any example:
Capacity = 7
wt = [3, 2, 4, 5, 1]
val = [50,40,70,80,10]
We build
- dp[i][w] = max value using the first i items with capacity w
- Rows → items (0 → 5)
- Columns → capacity (0 → 7)
DP Table Structure
Capacity →
Items ↓ 0 1 2 3 4 5 6 7
Base Row (0 items)
i = 0 (no items)
0 1 2 3 4 5 6 7
dp[0] = 0 0 0 0 0 0 0 0
Item 1: wt=3, val=50
i = 1
0 1 2 3 4 5 6 7
dp[1] = 0 0 0 50 50 50 50 50
Explanation: Capacity ≥ 3 → take item → value = 50
Item 2: wt=2, val=40
i = 2
0 1 2 3 4 5 6 7
dp[2] = 0 0 40 50 50 90 90 90
Key cells: dp[2][5] = max(50, 40 + dp[1][3]=50) = 90
Item 3: wt=4, val=70
i = 3
0 1 2 3 4 5 6 7
dp[3] = 0 0 40 50 70 90 110 120
Key cells:
dp[3][6] = 70 + dp[2][2] = 110
dp[3][7] = 70 + dp[2][3] = 120
Item 4: wt=5, val=80
i = 4
0 1 2 3 4 5 6 7
dp[4] = 0 0 40 50 70 90 110 120
Item 4 does not improve any capacity.
Item 5: wt=1, val=10
i = 5
0 1 2 3 4 5 6 7
dp[5] = 0 10 40 50 70 90 110 120
Final Answer
Maximum value at capacity 7 = dp[5][7] = 120
One optimal selection:
wt 3 (50)
wt 4 (70)
→ total weight = 7
→ total value = 120Full Dp Table
w → 0 1 2 3 4 5 6 7
i ↓
0 0 0 0 0 0 0 0 0
1 (3,50) 0 0 0 50 50 50 50 50
2 (2,40) 0 0 40 50 50 90 90 90
3 (4,70) 0 0 40 50 70 90 110 120
4 (5,80) 0 0 40 50 70 90 110 120
5 (1,10) 0 10 40 50 70 90 110 120
Code
def knapsack(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(1,capacity+1):
if weights[i-1]<=w:
dp[i][w] = max(dp[i-1][w],values[i-1] + dp[i-1][w-weights[i-1]])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
weights = [3, 4, 5]
values = [30, 50, 60]
capacity = 8
result = knapsack(weights, values, capacity)
print(f"Maximum value: {result}") # Output: 90