knapsack problem

The problem of choosing items, each with a weight and a value, to maximise total value without exceeding a weight capacity.

In more detail

In the 0/1 version each item is taken whole or not at all, and greedy by value-per-weight can fail. Dynamic programming fills a table where cell [i][w] is the best value using the first i items within capacity w, taking O(n × W) time. The course's three items and capacity four give a five-by-five table.

Related terms

Taught in

References