the 0/1 knapsack DP

You have a backpack that can carry at most W units of weight and a set of n items, each with a weight and a value. Each item is either taken whole or left behind — you cannot take a fraction of one, hence '0/1'. You want the most valuable selection of items that still fits in the weight limit. This is the classic problem where being greedy fails: grabbing items by best value-to-weight ratio can overshoot or waste capacity, so you genuinely need to consider combinations, and dynamic programming is the clean way to do it.

The state is dp[i][w] = the maximum value achievable using only the first i items with a weight budget of w. The transition at item i considers two cases. You can skip item i, leaving dp[i-1][w] unchanged. Or, if item i fits (weight[i] <= w), you can take it, gaining value[i] plus the best you can do with the first i-1 items and the reduced budget w - weight[i]. So dp[i][w] = max( dp[i-1][w], value[i] + dp[i-1][w - weight[i]] ), with base case dp[0][w] = 0 for all w (no items, no value). Filling the table over i from 1 to n and w from 0 to W gives O(nW) time and O(nW) space; since each row depends only on the previous one, you can compress to O(W) space by overwriting a single array from high w down to low w (the downward direction is essential so each item is used at most once).

Two honest cautions matter here. First, O(nW) looks polynomial but W is a number written in roughly log W bits, so the running time is exponential in the input's bit-length — this is called pseudo-polynomial, and it is why 0/1 knapsack is NP-hard despite this neat table: the algorithm is only efficient when W is small. Second, this is the textbook case where greedy is wrong: the fractional knapsack is solved optimally by the greedy ratio rule, but the 0/1 version is not, which is a vivid reminder that 'take the locally best item' is not a proof of optimality. The DP, by contrast, is provably correct via optimal substructure.