The Problem#

You have a backpack that can carry at most W kilograms, and n items each with a weight and a value. You want to fill the pack to maximise total value without exceeding the weight limit. Each item is either fully taken or fully left. You cannot take a fraction of an item. That restriction is the "0/1" in the name.

Brute force: try every subset of items. With n items there are 2ⁿ subsets. That's exponential, and hopeless for large inputs.

The DP observation: the value you can achieve depends only on which items you have considered so far and how much capacity remains. Those two quantities define a subproblem.