0/1 Knapsack Problem using
Dynamic Programming
Design and Analysis of Algorithms
DYNAMIC PROGRAMMING
Man Gajjar - 24002171220007
PROBLEM DEFINITION
The 0/1 Knapsack Problem
Problem Statement
Given n items, each with a specific weight
and value, and a knapsack with maximum
capacity W, determine the maximum value
achievable by selecting items without
exceeding the capacity.
The Key Constraint
Each item can be either included (1) or
excluded (0) — no fractional quantities
allowed.
Real-world example: A hiker packing
essentials with limited bag capacity,
choosing items that maximize utility.
Why Dynamic Programming?
Overlapping Subproblems Optimal Substructure Why Greedy Fails
The same subproblems are solved The optimal solution can be Selecting items by value-to-weight
multiple times when using naive constructed from optimal solutions ratio doesn't guarantee optimal
recursion. DP stores solutions to of its subproblems. If we know the results in 0/1 knapsack. A greedy
avoid redundant calculations, best way to pack lighter loads, we choice might block better
dramatically improving efficiency. can build up to the full capacity. combinations later.
DP Table Formulation
Understanding DP[i][w]
DP[i][w] represents the maximum value
achievable using the first i items with a
knapsack capacity of w.
Rows (i): Items considered (0 to n)
Columns (w): Capacity levels (0 to W)
Include Item Update DP Exclude Item Select Max
The Recurrence Relation
Adding a new element Recalculating based Removing an element Choosing the optimal
to the set. on the new item. from the set. final value.
For each item i and capacity w:
DP [i][w] =
⎧0 if i = 0 or w = 0
⎨DP [i − 1][w] if weight[i] > w
⎩
max(DP [i − 1][w], value[i] + DP [i − 1][w − weight[i]]) otherwise
WORKED EXAMPLE
Building the DP Table
Consider 4 items with capacity W = 7:
Item 1 Item 2 Item 3 Item 4
Weight: 1 Weight: 3 Weight: 4 Weight: 5
Value: 1 Value: 4 Value: 5 Value: 7
Item\Cap 0 1 2 3 4 5 6 7
acity
0 (none) 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 1
(w=1,v=1)
2 0 1 1 4 5 5 5 5
(w=3,v=4)
3 0 1 1 4 5 6 6 9
(w=4,v=5)
4 0 1 1 4 5 7 8 9
(w=5,v=7)
Each cell is calculated by choosing the maximum between including or excluding the current item.
Solution & Backtracking
9
Maximum Value
Found at DP[4][7]
Items Selected
By tracing back through the table, we identify which items were included:
Item 3 (w=4, v=5) Item 2 (w=3, v=4)
Total weight: 7 (exactly at capacity)
Total value: 9 (optimal solution)
Backtracking Logic
Start from DP[n][W] and move backwards:
1. If DP[i][w] ≠ DP[i-1][w], item i was included
2. Subtract item's weight from current capacity
3. Move to DP[i-1][w - weight[i]]
4. Repeat until reaching DP[0][0]
ALGORITHM
Pseudocode
function Knapsack(weights[], values[], n, W):
// Initialize DP table with zeros
DP[0...n][0...W] = 0
// Fill the DP table
for i = 1 to n:
for w = 0 to W:
if weights[i-1] <= w:
// Choose max of include or exclude
DP[i][w] = max(
values[i-1] + DP[i-1][w - weights[i-1]], // include item
DP[i-1][w] // exclude item
)
else:
// Item cannot fit, exclude it
DP[i][w] = DP[i-1][w]
// Maximum value is at bottom-right corner
return DP[n][W]
Complexity & Key Takeaways
Time Complexity Space Complexity Optimal Solution
O(n × W) O(n × W) DP guarantees finding the maximum
value for any valid input
Filling a table with n rows and W Storage for the DP table (can be
columns optimized to O(W))
Key Insight: Dynamic programming transforms an exponential brute-force problem into a polynomial-time solution by
systematically building optimal solutions from smaller subproblems.
Best suited when capacity W is reasonable. For very large W, consider approximation algorithms or space-optimized variants.