The Knapsack Problem

By the end, you can

• Explain why greedy by value/weight ratio fails for 0/1 knapsack but is optimal for the fractional variant.
• Define dp[i][w] and state the take-or-skip recurrence, including the base case and the case when an item is too heavy.
• Fill in any row of the 0/1 knapsack DP table by hand, applying the recurrence cell by cell.
• Read the optimal value from the bottom-right cell and trace back through the table to identify which items were selected.
• Identify the single character change that converts the 0/1 recurrence into the unbounded recurrence.
• Explain why the algorithm is pseudo-polynomial and why 0/1 knapsack is NP-hard.
• Apply the 1-D space optimisation and state why scanning direction differs between 0/1 and unbounded.