Knapsack Problem
The 0/1 Knapsack problem finds the maximum value that can be obtained with a given weight constraint using dynamic programming.
AdvancedTime: O(n × W)Space: O(n × W)
Take QuizItems
Gold BarW: 4, V: 10
Silver RingW: 2, V: 4
DiamondW: 3, V: 7
RubyW: 1, V: 2
PearlW: 2, V: 5
Step 1 / 0
Current Step
Click Play to start the visualization
## How 0/1 Knapsack Works
The 0/1 Knapsack problem asks: given items with weights and values, what's the maximum value you can carry with a weight limit? Each item can be taken (1) or left (0).
### Algorithm Steps:
1. Create a DP table of size (n+1) x (W+1)
2. For each item i and capacity w:
- If item weight > w: dp[i][w] = dp[i-1][w]
- Else: dp[i][w] = max(exclude item, include item)
3. Backtrack to find selected items
### Key Characteristics:
- **2D DP Table**: Items x Capacity
- **Choice**: Include or exclude each item
- **Applications**: Resource allocation, budget planning, cutting stock
Time & Space Complexity
| Case | Time Complexity |
|---|---|
| Best | O(n × W) |
| Average | O(n × W) |
| Worst | O(n × W) |
| Space | O(n × W) |
Practice Problems
10 problems81 total points
1
0/1 Knapsack Problem
Beginner5 pts
2
Subset Sum Problem
Beginner5 pts
3
Partition Equal Subset Sum
Beginner5 pts
4
Coin Change
Intermediate8 pts
5
Coin Change II
Intermediate8 pts
6
Target Sum
Advanced10 pts
7
Last Stone Weight II
Advanced10 pts
8
Profitable Schemes
Advanced10 pts
9
Ones and Zeroes
Advanced10 pts
10
Maximum Value of K Coins From Piles
Advanced10 pts