0/1 Knapsack
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Ready
Capacity
5
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
You are a thief with a knapsack that can hold a maximum weight W. You have a list of items, each with a weight and a value. For each item, you have to decide: take it or leave it? You cannot break an item (hence "0/1"). The goal is to maximize the total value without bursting the knapsack.
Concept
Dynamic Programming Approach:
We define `dp[i][w]` as the maximum value achievable using a subset of the first i items with a remaining capacity of w.
Recurrence Relation:
- Don't include item i: Value is same as without it: `dp[i-1][w]`.
- Include item i (if weight[i] <= w): Value is current item's value + max value with remaining capacity: `value[i] + dp[i-1][w - weight[i]]`.
We take the maximum of these two choices.
How it Works
Tabulation Algorithm:
- Initialize a table `dp` of size (n+1) \times (W+1) with 0s.
- Iterate through items i from 1 to n.
- Iterate through capacity w from 0 to W.
- For each cell, apply the recurrence relation to maximize value.
- The final answer is stored in `dp[n][W]`.
Step-by-Step Breakdown
Visualizing the table:
- Rows: Represent the items available so far.
- Columns: Represent the current capacity limit.
- Cell Value: Best value achievable for that subproblem.
- Result: Bottom-right cell contains the global maximum.
When to Use
Applications:
- Resource allocation with budget constraints.
- Cargo loading problems.
- Selection problems (e.g., cutting stock).
When NOT to Use
- Fractional Items: If you can take parts of an item, use the Greedy approach (Fractional Knapsack).
- Huge Capacity: If W is extremely large (10^9), the O(nW) space/time is too slow (pseudo-polynomial).
How to Identify
"Maximize value", "Weight limit", "Pick items", "Cannot break items".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.