WRITE · TRACE · UNDERSTAND
0/1 Knapsack
Fill a capacity table without taking an item twice
Your experiment
pack(items, capacity) returns the maximum value of items that fit. Each (weight, value) item may be taken once; weights are positive and values nonnegative.
Python runs in your browser. Your draft stays on this device.
What to look for
The table records the best value at each capacity. Iterate capacity downward so each transition reads a state that has not used the current item. Trace upward updates to see why they would solve an unbounded problem instead.
Watch your code work
Ready to experimentWrite a solution or load the worked answer, then choose Trace & check.
Step through arrays, variables and training curves produced by your own Python.