LESSON 28 · PATTERN GUIDE

Knapsack / Subset DP

Track which capacities, sums, or resource combinations are reachable as items are considered.

FIRST, LEARN THE PATTERNFor each item, choose whether to take it or skip it. A DP state records the best value or reachability for a capacity or sum.

Items have weights, values, counts, or a target sum, and each item may be chosen under constraints.

How to approach it

Write the state and transition first. For 0/1 items with 1D compression, iterate capacity downward so the same item is not reused.

Watch out for

Loop direction changes whether items can be reused. Large numeric targets may make pseudo-polynomial DP impractical.

A CLOSER EXPLANATION

Each item creates a take-or-skip decision, and DP combines the choices while tracking capacity or reachable sums. In 0/1 knapsack, a one-dimensional capacity array is updated downward so an item cannot feed into itself during the same iteration. Unbounded knapsack often uses the opposite loop direction.

NOW YOU TRY

Practice question

Can [1, 4, 6, 9] be split into two groups with equal sums?

EXAMPLEvalues = [1, 4, 6, 9], total = 20Give your answer before revealing the explanation.

Show a hint

If the total is even, look for a subset summing to half the total.

Show an answer

Yes. One group is [1, 9] and the other is [4, 6].

CONNECT IT TO REAL LIFE

Knapsack / Subset DP at work

A team has a $10,000 budget and project costs [6,000, 5,000, 4,000]. What is the most money it can spend without exceeding the budget?

Show one possible approach

$10,000, selecting the $6,000 and $4,000 projects. A subset-sum DP tracks which totals are reachable as each project is considered.

Practice next

Use these problem IDs to find additional practice for this pattern:

4164945184741049879