0/1 Knapsack

You have n items. Item j (0-based) has weight w[j] and value v[j]. Knapsack capacity is W. Each item may be used at most once. Maximize total value without exceeding W.

Let dp(i, c) = maximum value using only items 0, 1, …, i−1 (the first i items) with total weight at most c.

For i ≥ 1 and c ≥ 0:

• Skip item i−1: value dp(i − 1, c).
• Take item i−1 (only if w[i−1] ≤ c): value v[i−1] + dp(i − 1, c − w[i−1]).

Explanation: Any optimal solution for the first i items either does not use item i−1 (first term) or uses it once (second term); smaller subproblems use only the first i − 1 items.

Use a 2D table memo[0…n][0…W] (or a map) with −1 meaning unknown. dp(i, c) only calls dp(i − 1, ·) with the same or smaller capacity, so i strictly decreases along one branch — recursion always moves toward i = 0.

Fill memo[i][c] the first time you compute it. There are (n + 1)(W + 1) states, O(1) work each — O(nW) time, O(nW) space for memo plus stack O(n).

Explanation: With zero items available, the best value is 0 no matter the capacity. All recursion eventually reaches i = 0.

Top-down:

Time: O(nW). Space: O(nW) for memo (iterative 1D rolling is a separate implementation trick, not shown here).