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 decision-makers must choose from a set of indivisible 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 optimisation:
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?
(0,7)
/ Take1 \ Skip1
(1,6) (1,7)
/ \ / \
Take3 (2,3) Skip3 (2,6) Take3 (2,4) Skip3 (2,7)
/ \ / \ / \ / \
Skip4 Skip4 Take4 Skip4 Take4 Skip4 Take4 Skip4
(3,3) (3,3) (3,2) (3,6) (3,0) (3,4) (3,3) (3,7)
| | | | | | | |
Skip5 Skip5 Skip5 Take5 End Skip5 Skip5 Take5
Logic
(i, W)
|
weight[i] <= W ?
/ \
YES NO
/ \ \
TAKE SKIP SKIP
(i+1, W-wt[i]) (i+1, W) (i+1, W)
- Each node represents (i, W) → current index and remaining capacity.
- At every item, check: weight[i] <= W.
- If true → two options:
- Take the item
- Skip the item
- If false → only one option:
- Skip the item
- After each decision → move to i + 1.
- Stop when i == n or W == 0.
- Maximum possibilities ≈ 2^n.
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) # no. of elements
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,capacity+1):
if weights[i-1]<=w=j:
dp[i][j] = max(dp[i-1][j],values[i-1] + dp[i-1][j-weights[i-1]])
else:
dp[i][j] = dp[i-1][j]
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
Algorithm
1. Create a 2D array dp of size (n+1) × (W+1)
2. Initialize:
For w = 0 to W:
dp[0][w] = 0
(If no items → value = 0)
3. For i = 1 to n:
For w = 0 to W:
If weight[i] > w:
dp[i][w] = dp[i-1][w] // Cannot take item
Else:
dp[i][w] = max(
dp[i-1][w], // Skip
value[i] + dp[i-1][w - weight[i]] // Take
)
4. Return dp[n][W]0/1 Knapsack(6 Variation)
Variation 1: Subset Sum
You are given an array of positive integers, arr[] and a number K (target sum). Is there a subset of the array whose sum is exactly K?
arr = [2, 3, 7, 8, 10]
K = 11
3 + 8 = 11 # Yes
arr = [1, 2, 3]
K = 4
DP Table
arr = [1, 2, 3]
K = 4
| Item \ Sum | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 items | T | F | F | F | F |
| Item 1 (1) | T | T | F | F | F |
| Item 2 (2) | T | T | T | T | F |
| Item 3 (3) | T | T | T | T | T |
Tabulation:2D Version
def subset_sum(nums, target):
length = len(nums)
dp = [[False]*(target+1) for _ in range(length+1)]
# Base case
for i in range(length+1):
dp[i][0] = True # target 0 is always possible
for i in range(1, length+1):
for j in range(1, target+1):
if j >= nums[i-1]:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[length][target]Tabulation: 1D Version
def subset_sum(nums, target):
dp = [False] * (target + 1)
dp[0] = True # sum 0 always possible
for num in nums:
for j in range(target, num - 1, -1): # backward
dp[j] = dp[j] or dp[j - num]
return dp[target]Recursion: Forward Index
def subset(i, target):
if target == 0:
return True
if i == n or target < 0:
return False
return (
subset(i+1, target) or
subset(i+1, target-nums[i])
)
Recursion: Backward Index
def subset_sum(nums, n, target):
# Base cases
if target == 0:
return True
if n == 0:
return False
# If current element is greater than target, skip it
if nums[n - 1] > target:
return subset_sum(nums, n - 1, target)
# Choice: take OR skip
return (
subset_sum(nums, n - 1, target) or
subset_sum(nums, n - 1, target - nums[n - 1])
)
# Example
nums = [1, 2, 3]
K = 4
print(subset_sum(nums, len(nums), K))
| Feature | Forward Index | Backward Index |
|---|---|---|
| Direction | Left → Right | Right → Left |
| Parameter | i (index) | n (size) |
| Base Stop | i == n | n == 0 |
| Array Access | nums[i] | |
| Negative Check | Needs target < 0 | Avoided via |
Variation 2: Partition Equal Subset Sum
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Leetcode 416. Partition Equal Subset Sum
Example
nums = [1, 2, 3]
[1,2] and [3] #sum of both subset 3Logic
We need to divide it into 2 subsets such that: subset1 sum = subset2 sum
Note:
- Every element in the array must belong to either subset 1 or subset 2.
- No element can be left unused.
sum1 = sum2
or say
Total(sum of element) = sum1+sum2
Total = 2*sum1
We can say total will be alway be even
Case 1: Equal partition not possible is total is odd
Case 2:
total = 2 × subset1 = S
subset1 = total//2
So, Target = total//2
finding sum till total//2 is enough
example
nums = [1, 5, 11, 5]
total = 22
But we only need to know whether 11 is possible.
Everything after 11 (12,13,...22) is irrelevant as sum1 =sum2DP Table
| i \ Sum | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 items | T | F | F | F |
| 1 (1) | T | T | F | F |
| 2 (2) | T | T | T | T |
| 3 (3) | T | T | T | T |
Tabulation:2D Version
def subset_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
length = len(nums)
dp = [[False]*(target+1) for _ in range(length+1)]
# base case
for i in range(length+1):
dp[i][0] = True
for i in range(1, length+1):
for j in range(1, target+1):
if j >=nums[i-1]:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[length][target]
Tabulation:1D Version
def subset_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False]*(target+1)
dp[0] = True
for num in nums:
for j in range(target, num-1, -1):
dp[j] = dp[j] or dp[j-num]
return dp[target]Doubts: If we have reached the target sum, how do I know the other half is there as well?
Because:
- Every element in the array must belong to either subset 1 or subset 2.
- No element can be left unused.
Variant 3: Count of Subsets with Given Sum
How many subsets give exactly the target sum?
nums = [1, 2, 3, 3]
target = 6
{1,2,3} (first 3)
{1,2,3} (second 3)
{3,3}
Answer = 3DP Table
nums = [1, 2]
target = 2
| i \ j | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 |
Tabulation:2D Version
def count_subset_sum(nums, target):
length = len(nums)
dp = [[0] * (target + 1) for _ in range(length + 1)]
for i in range(length+1):
dp[i][0] = 1
for i in range(1, length + 1):
for j in range(target + 1):
if j>=nums[i-1]:
dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[length][target]Tabulation:1D Version
def count_subset_sum(nums, target):
dp = [0] * (target + 1)
# equivalent to dp[i][0] = 1 for all i
dp[0] = 1
for num in nums:
for j in range(target, -1, -1):
if j >= num:
dp[j] = dp[j] + dp[j - num]
return dp[target]
Variant 4: Minimum Subset Sum Difference
Given the array nums, divide into 2 subsets such that abs(sum(S1)−sum(S2) is minimum
nums = [1, 6, 11, 5]
Logic
We already have
s1 + s2 = sum(nums) #total
s1 = total-s2
putting in our equation s1-s2
2*s1-total ==> min.
or
abs(total-2*s1) => min
abs(sum(S1)−sum(S2) ==> abs(total-2*sum(S1))
Find subset sum s1 such that |S - 2*s1| is minimum.Tabulation:2D Version
def min_subset_difference(nums):
total = sum(nums)
length = len(nums)
dp = [[False]*(total+1) for _ in range(length+1)]
for i in range(length+1):
dp[i][0] = True
for i in range(1, length+1):
for j in range(1, total+1):
if j>=nums[i-1]:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
min_diff = float('inf')
for s1 in range(total//2 + 1): #
if dp[length][s1]:
min_diff = min(min_diff, abs(total - 2*s1))
return min_diff
for s1 in range(total//2 + 1):
We only need to check subset sums up to: total//2, Because after that difference starts increasing again.Tabulation:1D Version
def min_subset_difference(nums):
total = sum(nums)
dp = [False]*(total+1)
dp[0] = True
for num in nums:
for j in range(total, num-1, -1):
dp[j] = dp[j] or dp[j-num]
min_diff = float('inf')
for s1 in range(total//2 + 1):
if dp[s1]:
min_diff = min(min_diff, abs(total - 2*s1))
return min_diff
DP Table
nums = [1, 2, 3]
| i \ j | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | T | F | F | F |
| 1 (1) | T | T | F | F |
| 2 (2) | T | T | T | T |
| 3 (3) | T | T | T | T |
Why do we need a full range in DP, while we search till total//2 only?
It’s fine, we can calculate dp till total//2
Variant 5: Target Sum
Given an array nums and a target S, assign + or – to each number so that the total equals S.
Return the number of ways.
Logic
Target sum --> Convert to Subset Problem
nums = [a1, a2, a3, ...]
t = sum(nums) => p + n # equation 1
p : all positive
n : all negative
Given,
s = p-n #equation 2
adding equation 1 and 2
t+s = 2*p
required sub set sum (p) = (t+s)//2
Tabulation:2D Version
def target_sum(nums, target):
total = sum(nums)
# invalid cases
if abs(target) > total:
return 0
if (target + total) % 2 != 0:
return 0
subset_sum = (target + total) // 2
n = len(nums)
# dp[i][j] = number of ways to get sum j using first i elements
dp = [[0] * (subset_sum + 1) for _ in range(n + 1)]
# base case
dp[0][0] = 1 # one way to make sum 0 with 0 elements
for i in range(1, n + 1):
for j in range(subset_sum + 1):
# skip current number
dp[i][j] = dp[i-1][j]
# take current number (if possible)
if j >= nums[i-1]:
dp[i][j] += dp[i-1][j - nums[i-1]]
return dp[n][subset_sum]
Tabulation:1D Version
def target_sum(nums, target):
total = sum(nums)
# invalid cases
if abs(target) > total:
return 0
if (target + total) % 2 != 0:
return 0
subset_sum = (target + total) // 2
dp = [0] * (subset_sum + 1)
dp[0] = 1
for num in nums:
for j in range(subset_sum, num-1, -1):
dp[j] += dp[j - num]
return dp[subset_sum]Variant 6: No. of subsets of a given difference
Given an array of positive integers, nums and an integer diff, find the number of subsets such that the difference between the sum of two subsets is equal to diff.
i.e S1−S2=diff: return the count of such possible subset partitions.
Input:
nums = [1, 1, 2, 3]
diff = 1
Output:
3
{1(index 0),1(index 1),2} and {3}
{1(index 0),2} and {1(index 1),3}
{1(index 1),2} and {1(index 0),3} (different index 1)
Logic
s1 - s2 = diff
s1 + s2 = total
s1 = (diff+total)//2
Problem becomes =>Count subsets with sum = (total + d) // 2Tabulation:2D Version
def count_subset_difference(nums, d):
total = sum(nums)
if d > total:
return 0
if (total + d) % 2 != 0:
return 0
target = (total + d) // 2
n = len(nums)
dp = [[0]*(target+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(target+1):
# skip
# take
if j >= nums[i-1]:
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]
Tabulation:1D Version
def count_subset_difference(nums, d):
total = sum(nums)
if d > total:
return 0
if (total + d) % 2 != 0:
return 0
target = (total + d) // 2
dp = [0]*(target+1)
dp[0] = 1
for num in nums:
for j in range(target, num-1, -1):
dp[j] += dp[j-num]
return dp[target]Unbounded Knapsack
Converting 0/1 → Unbounded Knapsack
| Feature | 0/1 Knapsack | Unbounded Knapsack |
|---|---|---|
| Item usage | Only once | Unlimited times |
| Transition | dp[i-1][...] | dp[i][...] |
| Row movement | Move up after taking dp[i-1][j-w] | Stay in the same row dp[i][j] = dp[i][j-w] |
| Loop direction (1D) | Reverse | Forward |
2D DP Transition Change
0/1 Knapsack
dp[i][j] = dp[i-1][j] # don't take
+ dp[i-1][j-w] # take once
Unbounded Knapsack
dp[i][j] = dp[i-1][j] # don't take
+ dp[i][j-w] # take again allowed
i-1 in 0/1: Because after taking, we cannot reuse that item.
i in ubounded: Because after taking, we are still allowed to use that item again.
Recursion Identity Shift
0/1
take = solve(i-1, remaining - weight)
Unbounded
take = solve(i, remaining - weight)1D DP Loop Direction Shift
0/1 Knapsack (Reverse loop)
for w in range(capacity, weight-1, -1):
Unbounded Knapsack (Forward loop)
for w in range(weight, capacity+1):0/1 reverse: To prevent reusing the same item in the same iteration.
unbounded forward: Because we WANT to reuse the item.
One-Line Master Rule
- If you are allowed to reuse an item → stay on the same row
- If not allowed → move to previous row
Variant 1: Coin Change – Number of Ways
Return the fewest number of coins that you need to make up that amount.
def coinChange(coins, amount):
length = len(coins)
dp = [[float('inf')]*(amount+1) for _ in range(length+1)]
# Base case
for i in range(length+1):
dp[i][0] = 0
for i in range(1, length+1):
for j in range(1, amount+1):
if j >= coins[i-1]:
dp[i][j] = min(
dp[i-1][j], # don't take
1 + dp[i][j-coins[i-1]] # take (unbounded)
)
else:
dp[i][j] = dp[i-1][j]
return -1 if dp[length][amount] == INF else dp[length][amount]
Base condition : d[i….][0] = 0: required amount 0, there is no way, i.e., 0
1 + dp[i][j-coins[i-1]]: 1 is used to add 1 coin to the count of coins
def coinChange(coins, amount):
INF = float('inf')
dp = [INF] * (amount + 1)
dp[0] = 0
for coin in coins:
for j in range(coin, amount + 1):
dp[j] = min(dp[j], 1 + dp[j - coin])
return dp[amount] if dp[amount] != INF else -1
or both are same
def coinChange(coins, amount):
dp = [float('INF')]*(amount+1)
dp[0] = 0
for i in range(1,amount+1):
for c in coins:
pos = i-c
if pos>=0:
dp[i] = min(dp[pos]+1,dp[i])
if dp[amount] == float('inf'):
return -1
return dp[amount]Variant 2: Coin Change – Number of Ways
Return the number of combinations that make up that amount.
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+12D
def change(amount, coins):
length = len(coins)
# dp[i][j] = ways to form j using first i coins
dp = [[0] * (amount + 1) for _ in range(length + 1)]
# Base case: amount 0 can always be formed
for i in range(length + 1):
dp[i][0] = 1
for i in range(1, length + 1):
for j in range(1, amount + 1):
if j >= coins[i - 1]:
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[length][amount]1d
def change(amount,coins):
dp = [0] * (amount + 1)
dp[0] = 1 # Base case: one way to make amount 0
for coin in coins: # outer loop = coins
for j in range(coin, amount + 1): # forward loop
dp[j] = dp[j] + dp[j - coin]
return dp[amount]
Variant 3: Rod Cutting
You are given a rod of length N and a price array where price[i] = price of the rod piece of length i + 1
- You can cut the rod into smaller pieces in any combination.
- You can use the same length piece multiple times.
- Goal: Maximise total profit.
Rod length = 5
price = [2,5,7,8]
Best = 12Code
def rod_cutting(price, n):
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if i <= j:
dp[i][j] = max(
dp[i-1][j], # skip
price[i-1] + dp[i][j-i] # take
)
else:
dp[i][j] = dp[i-1][j]
return dp[n][n]
Let’s make it similar to the classic knapsack. We normally give a price array p.
P[3] means price for length 4, as the length array is not given, we can take it as
- length = [1,2,3,4]
- price =[2,5,7,8]
Compared to the classic knapsack
- length –> wieght
- price –> value
Code
def rod(price, length, target):
n = len(price)
dp = [[0]*(target+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, target+1):
if length[i-1] <= j:
dp[i][j] = max(
dp[i-1][j],
price[i-1] + dp[i][j-length[i-1]]
)
else:
dp[i][j] = dp[i-1][j]
return dp[n][target]1D code
def rod_cutting(price, n):
dp = [0] * (n + 1)
for i in range(1, n + 1): # piece length = i
for j in range(i, n + 1): # rod length
dp[j] = max(
dp[j],
price[i-1] + dp[j-i]
)
return dp[n]Variant 4: Integer Break
Given an integer n, break it into at least two positive integers such that their product is maximised. Return the maximum product you can get.
Example:
| n | Best Split | Product |
|---|---|---|
| 2 | 1 + 1 | 1 |
| 3 | 2 + 1 | 2 |
| 4 | 2 + 2 | 4 |
| 5 | 3 + 2 | 6 |
| 6 | 3 + 3 | 9 |
| 7 | 3 + 4 | 12 |
| 8 | 3 + 3 + 2 | 18 |
| 9 | 3 + 3 + 3 | 27 |
| 10 | 3 + 3 + 4 | 36 |
2D
def integerBreak(n):
dp = [[0]*(n+1) for _ in range(n)]
# base case
for i in range(n):
dp[i][0] = 1
for i in range(1, n): # numbers 1 to n-1
for s in range(1, n+1):
# not take
dp[i][s] = dp[i-1][s]
# take (unbounded)
if s >= i:
dp[i][s] = max(
dp[i][s],
i * dp[i][s - i]
)
return dp[n-1][n]1D
def integerBreak(n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
max_product = 0
for j in range(1, i):
# don't break remaining part
no_break = j * (i - j)
# break remaining part further
break_further = j * dp[i - j]
max_product = max(max_product, no_break, break_further)
dp[i] = max_product
return dp[n]Add finding subset to form that subset ??? Check it out, it’s possible or not.
Warm up
Subset Sum (Boolean)
698. Partition to K Equal Sum Subsets
417 Partition to K Equal Sum Subsets — Medium/Hard
418 Matchsticks to Square — Medium
Count of Subsets (0/1 Counting)
- Target Sum — Medium
- Number of Dice Rolls With Target Sum — Medium (similar counting idea)
- Combination Sum IV — Medium (be careful: order matters → different DP)
Minimum Difference / Partition Type
- Last Stone Weight II — Medium
- Partition Array Into Two Arrays to Minimise Sum Difference — Hard
Pure 0/1 Knapsack Core
- Ones and ZZeros— Medium (2D knapsack)
- Profitable Schemes — Hard
- Minimise the Difference Between Target and Chosen Elements — Medium
Count Partitions with Given Difference (Indirect)
- Target Sum — Medium (same reduction)
- Distribute Repeating Integers — Hard (bitmask + subset logic)
Direct Subset DP Practice
- Word Break — Medium (boolean DP pattern)
- Coin Change — Medium (unbounded version)
- Coin Change II — Medium (counting version)
1 thought on “Knapsack — The Master DP Pattern”