0/1 Knapsack Family
State is index plus remaining capacity. Each item is either taken or skipped, and the table is filled over both dimensions.
Dynamic ProgrammingO(n * W)New6 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
subset sum
partition equal subset
target sum
pick items under a budget
The template
Get this into muscle memory, then adapt the condition per problem.
for (let i = 1; i <= n; i++)
for (let w = 0; w <= W; w++)
dp[i][w] = Math.max(dp[i-1][w], wt[i-1] <= w ? val[i-1] + dp[i-1][w - wt[i-1]] : 0); Watch 0/1 KnapsackIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Each item has a binary decision and a shared budget.
- 2Two dimensions: how many items considered, how much capacity is left.
- 3Iterate capacity downward to reuse a single row.
Drill it
Every problem in the bank that uses this pattern.
0 / 6 solved