203. 0/1 Knapsack Problem

Given n items, each with a weight and a value, and a knapsack of capacity W, find the maximum total value obtainable by choosing a subset of items (each item taken whole or not at all) whose total weight doesn't exceed W.

Input: Four lines: n; n space-separated weights; n space-separated values; the knapsack capacity W. Output: Print a single integer - the maximum total value obtainable within capacity W.

1 <= n <= 1000, 1 <= W <= 10^4

The space-optimized 1D version MUST process capacities in DECREASING order when updating for each item - processing in increasing order would accidentally allow the SAME item to be used multiple times, turning it into unbounded knapsack by mistake.

Choose a subset of items (each taken whole or not at all) to maximize value without exceeding a weight capacity. Brute force: Try every one of the 2^n possible subsets directly, checking weight and computing value for each - this is exponential, impractical for n up to 1000. Optimised: The DP table captures the reusable insight that the best value using the first i items at capacity w only depends on smaller sub-problems (fewer items, or less capacity) - filling the table bottom-up computes every needed sub-answer exactly once, turning exponential subset enumeration into a table of n*W cells.

Define dp[i][w] = the maximum value achievable using only the first i items with capacity w. Fill this table bottom-up: dp[i][w] = dp[i-1][w] (skip item i) or, if item i's weight fits, also try value[i] + dp[i-1][w - weight[i]] (take item i), keeping the better of the two. Because each (i, w) state is computed exactly once from already-computed smaller states, this removes all the exponential recomputation of brute force. Time: O(n * W) Space: O(n * W)

Notice that dp[i][w] only ever depends on the previous row, dp[i-1][*], so a single 1D array of size W+1 suffices if updated carefully: for each item, iterate w from W down to that item's weight (descending order is essential so each item is only considered once per capacity, not reused). This computes the exact same values as the 2D table but overwrites the array in place, cutting memory from O(n*W) down to O(W) while keeping the same O(n*W) time - a meaningful saving since W can be up to 10^4. Time: O(n * W) Space: O(W)

Recursively consider every item with two choices - take it or skip it - branching into all 2^n subsets, tracking accumulated weight and value, and discarding any branch whose weight exceeds W; take the maximum value over all feasible subsets explored. This checks every possible subset exhaustively, guaranteeing correctness, but the same (item index, remaining capacity) situation gets recomputed many times across different branches, causing exponential growth. Time: O(2^n) Space: O(n) recursion depth

1. dp[i][w] = the best value achievable using the FIRST i items with capacity w. 2. For each item, either SKIP it (dp[i-1][w]) or TAKE it (dp[i-1][w-weight] + value, if it fits) - take the better of the two. 3. The final answer is dp[n][W].

Time: O(n * W) - filling the DP table, one cell per (item count, capacity) combination. Space: O(n * W) for the full table (reducible to O(W) with a rolling 1D array, processing capacities in DECREASING order to avoid reusing an item within the same pass).

Test n = 1 (take the single item only if it fits), every item's weight exceeding W (answer is 0), and n = 1000, W = 10^4 (upper bounds) for the DP table's size.

Be ready to contrast this with UNBOUNDED knapsack (items reusable) and FRACTIONAL knapsack (items splittable) - all three sound similar but need genuinely different techniques (0/1 needs this exact DP, unbounded allows same-row reuse, fractional is solved by a simple greedy).