DP -> Knapsack Family¶

Choose the state dimension and transition order that matches 0-1, complete, bounded, or value-based knapsack.

Microtopics¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Book Shop II	`CSES`	`Medium-Hard`	-	-	-	Bounded Knapsack; Multi-Copy	bounded-multiplicity knapsack variant

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Book Shop	`CSES`	`Easy`	0-1-Knapsack	Tabulation; Rolling-Array	Arrays; Maximization DP	Capacity; Value Maximization; Budget	The cleanest 0/1 knapsack template: maximize value under a budget with each item usable once.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Knapsack 1	`AtCoder DP Contest`	`Medium`	0-1-Knapsack	Tabulation	Book Shop; Nested Loops	Capacity; Value Maximization	The standard 0/1 knapsack formulation in its pure contest form.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Two Sets II	`CSES`	`Easy`	Subset Sum	Tabulation	Modular Arithmetic	Partition; Combinatorics	A classic partition-counting twist on subset-sum that reinforces exact-sum DP.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fruit Feast	`USACO Gold`	`Easy`	State-Augmented-Knapsack	Tabulation	Unbounded Knapsack; State Expansion	Unbounded; One-Time-State	A memorable knapsack twist where one optional action changes the reachable state space.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Minimizing Coins	`CSES`	`Easy`	Unbounded-Knapsack	Tabulation	Basic Recurrence; Arrays	Min-Coins; Unbounded; Min-Count	The simplest unbounded knapsack variant: minimize items while hitting an exact sum.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Coin Change	`LeetCode`	`Medium`	Unbounded-Knapsack	Tabulation	Minimizing Coins; Arrays	Min-Coins; Unbounded	The interview-friendly version of unbounded knapsack with the same core recurrence.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Coin Combinations I	`CSES`	`Easy`	Unbounded-Knapsack	Tabulation	Modular Arithmetic; Basic Counting	Counting; Order-Matters	Classic counting knapsack where the order of coins matters and the state is one-dimensional.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Talent Show	`USACO Gold`	`Hard`	Ratio-Optimization	Tabulation; Binary-Search-Check	0/1 Knapsack; Binary Search On Answer	Binary-Search-On-Answer	A classic knapsack variant that combines DP with an optimization ratio objective.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Money Sums	`CSES`	`Easy`	Subset Sum	Tabulation	Set Thinking; Boolean DP	Reachable-Sums; Bitset-Friendly	A classic subset-sum reachability problem that prepares you for bitset optimization later.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Target Sum	`LeetCode`	`Medium`	Counting-Knapsack	Tabulation	Subset Sum; Algebraic Transformation	Sign-Assignments; Counting	A classic transform-from-signs to subset-sum problem that rewards good state reframing.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Partition Equal Subset Sum	`LeetCode`	`Medium`	Subset Sum	Tabulation	Parity Checks	Partition; Boolean	A direct yes/no subset-sum target that helps cement knapsack as reachability.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Ones and Zeroes	`LeetCode`	`Medium`	2D-Knapsack	Tabulation	0/1 Knapsack; Counting Items	Dual-Capacity; 0-1	A useful multi-capacity knapsack that extends the standard single-budget template.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Coin Combinations II	`CSES`	`Easy`	Subset-Knapsack	Tabulation	Coin Combinations I; Modular Arithmetic	Counting; Order-Does-Not-Matter	Teaches the coin-ordering pitfall that distinguishes the two classic coin-change DPs.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Knapsack 2	`AtCoder DP Contest`	`Hard`	Value-Based-DP	Tabulation	0/1 Knapsack; State Redesign	Capacity; Value-State; Value-Based Knapsack; Large W	Shows the key trick of flipping the DP dimension when weights are too large.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`BOOKSHOP`	Book Shop	`primary`	`easy`	0 1 knapsack; downward capacity loop; budget value maximization	Note	Code

python3 scripts/generate_problem_catalog.py