🎒 0/1 Knapsack Problem

Problem

Given items with weights and values, and a knapsack with capacity W, find the maximum value you can carry without exceeding the weight limit. Each item can only be taken once (0/1 = take or leave).

Recurrence: $dp[i][w] = \max(dp[i-1][w], \; v_i + dp[i-1][w-w_i])$ if $w_i \le w$

Items (Capacity W = 7)

Click "Start" to fill the DP table

Complexity

Time: O(nW) where n = items, W = capacity
Space: O(nW) for the table (can be optimized to O(W))