Knapsack Variants: Include or Exclude

Concepts: pyKnapsack, pySubsetSum, pyCoinChange

Knapsack problems are the purest expression of the include/exclude DP paradigm. At each item, you make a binary decision: include it or exclude it. That decision plus the answer for remaining items and remaining capacity gives you the recurrence. Every knapsack variant, 0/1, unbounded, subset sum, multiple knapsack, is a variation on this single idea. Master the paradigm, not the individual problems. 0/1 Knapsack n items, each with weight w[i] and value v[i]. A bag with capacity W. Maximize total value without exceeding W. Each item is used at most once (0/1). dp[i][j] = max value using items 0..i-1 with capacity j. Either exclude item i (dp[i-1][j]) or include it if j >= w[i] (dp[i-1][j-w[i]] + v[i]). Unbounded Knapsack (Coin Change) Coin Change (LeetCode 322) is unbounded knapsack with m