How the 0/1 Knapsack DP Works

Top-down memoization and bottom-up tabulation solve the same recurrence; the difference is which subproblems get computed. mf_knapsack uses the global array f, initialized in the __main__ block with -1 for every cell that has not yet been computed. Line 17 is the memoization check: if f[i][j] is still -1, the subproblem is unseen and the function computes it. If f[i][j] already holds a non-negative value, the function returns it immediately. Line 18 covers the case where item i cannot fit at all (its weight exceeds remaining capacity j), so the best value is the same as with the previous items. Lines 21 through 23 encode the core decision: take the maximum of excluding item i (first branch) and including it (second branch, which reduces the remaining capacity by wt[i-1] and adds val[i-1]). The result is written back to f[i][j] before return so future calls skip the recursion.

Bottom-up DP fills every subproblem regardless of whether it is needed, and in exchange it avoids the overhead of recursion and global state. Line 30 allocates the table: an (n+1)-row, (W+1)-column list of zeroes. Row 0 is the base case (zero items, any capacity, zero value). Row i and column w hold the best achievable value using items 1 through i at capacity w. The outer loop walks items; the inner loop walks capacities. Line 34 checks whether item i-1 fits at the current capacity. If it fits, line 35 applies the inclusion/exclusion max: either take the item (using the previously computed value at reduced capacity) or skip it (keeping the row above). If it cannot fit, line 37 copies the row above unchanged. Line 39 returns the optimal value and the full table so the caller can trace back which items produced it.

This is the file's public API and the only function with a doctest, which is why it is the right stop for understanding the contract. The three examples cover the meaningful test surface. knapsack_with_example_solution(10, [1, 3, 5, 2], [10, 20, 100, 22]) returns (142, {2, 3, 4}): items at indices 2, 3, and 4 (weights 3, 5, 2) fit within capacity 10 and yield value 20+100+22=142. The second example at capacity 6 returns (8, {3, 4}). The third example deliberately passes mismatched list lengths and asserts a ValueError, which the contribution guide requires for all functions that can receive bad input. The doctest for the error case uses the Traceback (most recent call last): ... pattern that pytest's doctest runner understands as an expected exception.

Filling the table gives the optimal value; recovering which items produced it requires a separate backward pass. The function starts at cell (n, W) and asks a question at each step: did item i contribute to the optimal solution at this capacity? Line 127 compares the value in the row above (dp[i-1][j]) to the current cell (dp[i][j]). If they are equal, item i was not taken and the function recurses with i-1, keeping the same capacity j. If they differ, item i was included: line 130 adds i to the output set and recurses with capacity reduced by wt[i-1], because including item i consumed that weight. The base case on line 126 stops when either index reaches zero. Because multiple optimal subsets may exist (ties in the table), this traceback recovers one of them, not all of them, which is what the docstring says.

The block demonstrates the three functions together on a single concrete instance and uses assert to make the expected results machine-checkable. Items have weights [4, 3, 2, 3] and values [3, 2, 4, 4], and the bag holds capacity 6. Line 142 initializes the global table f that mf_knapsack reads: row 0 is all zeroes (the boundary condition where no items have been considered), and rows 1 through n+1 start at 0 in column 0 and -1 everywhere else. Both knapsack and mf_knapsack run on the same instance and print the same optimal value, confirming the two approaches agree. Lines 150 and 151 then assert that the optimal value is 8 and the recovered subset is items 3 and 4, which weigh 2+3=5 and yield value 4+4=8. Any regression in either the table fill or the traceback fails the assertion before the print lines execute.