Given a set of items each with a weight and value, and a bag of finite capacity, find the subset of maximum value that fits — no fractions, take each item at most once. This tool builds the classic O(nW) dynamic-programming table cell by cell, colours cells green when taking the item beats skipping it, and traces back through the table to show which items ended up in the optimal bag.
Row i, column w: best value achievable using the first i items with a bag of capacity w.
Recurrence: dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]]) when weight[i] ≤ w.
The 0/1 knapsack is NP-hard in general, but pseudo-polynomial in the capacity W — the DP runs in O(nW) time and space, fine for capacities into the low thousands but not for arbitrary integers (e.g. weights around 10⁹ break it). For continuous "fractional knapsack" the greedy value-to-weight ratio sort finds the optimum in O(n log n); it does not solve the 0/1 variant, which is why we need DP. If you only need the total value and not the picked set, the standard 1D optimisation reduces memory to O(W).