0/1 Knapsack Problem
Watch how 2D dynamic programming solves the classic optimization problem of maximizing value within weight constraints.
Time: O(n × W)
Space: O(n × W)
2D DP Table
Optimization
Fast (300ms)Slow (2000ms)
Progress: Step 1 of 0Phase: start
Items & Knapsack
Available Items
💎 Gem
2
3
📱 Phone
3
4
💻 Laptop
4
5
📷 Camera
5
6
Knapsack (0/10)
Empty knapsack
Total Weight: 0Total Value: 0
DP Table (Max Value)
Current Step:
Click Start to begin the 0/1 Knapsack visualization
Algorithm Details
Time Complexity:
O(n × W)Space Complexity:
O(n × W)Space Optimized:
O(W)Type:2D DP Table
Real-world Applications
- •Portfolio optimization in finance
- •Resource allocation in project management
- •Cargo loading optimization
- •Memory allocation in operating systems
- •Investment decision making
- •Feature selection in machine learning
Key DP Concepts
- ✓0/1 Constraint: Each item can be taken at most once
- ✓State: dp[i][w] = max value using first i items with capacity w
- ℹRecurrence: dp[i][w] = max(include, exclude)
- ℹBase Case: dp[0][w] = 0 (no items = no value)
Optimization Tips
- •Use 1D array for space optimization: O(W)
- •Process weights in reverse for 1D approach
- •Early termination if capacity exceeded
- •Sort items by value/weight ratio for heuristics