0/1 Knapsack Problem

George Dantzig, 1957

The knapsack problem, studied by George Dantzig and others from the late 1950s, asks: given items with weights and values, which subset maximizes total value without exceeding a capacity? The DP solution builds a table where each cell represents the best value achievable using the first i items with capacity w. The visualization fills the table cell by cell (gold for the current cell, teal for computed cells), then traces back to highlight which items were selected (coral).