Dynamic Programming21 sections · 916 units
Open in Course

0/1 Knapsack - Final Answer

Reading the table

After filling the entire table, where's your answer? You want the maximum value using all nn items with capacity at most WW. That's max(dp[n][0],dp[n][1],,dp[n][W])\max(dp[n][0], dp[n][1], \ldots, dp[n][W]). because of how the transition works, dp[n][W]dp[n][W] already contains this maximum.

Each state considers "capacity ww" as "up to ww", not "exactly ww". So dp[n][W]dp[n][W] is your final answer.