0/1 Knapsack Solver
AlgorithmsMediumChoose subsets of items to maximize values without exceeding weight limits.
Alt+Shift+K
Configuration Panel
Knapsack DP Grid (backtrack path highlighted)
DP table is empty.
Time Complexity
O(N * W)
Space Complexity
O(N * W) table space
Conceptual Overview
The 0/1 Knapsack problem limits items to selection count 0 or 1. Given items of weights and values, choose a subset that maximizes total value without exceeding total weight capacity W.
Recurrence Relation
dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]) if wt[i-1] <= w else dp[i-1][w]
State Transitions
Compares profit from adding item i (val[i-1] plus max profit from remaining weight w - wt[i-1]) against skipping item i (matching previous state dp[i-1][w]).
Source: CP-Algorithms dynamic programming reference