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
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- tabulation — Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.
- traceback — Walking back through a filled dynamic-programming table from the final cell to recover the choices that produced the optimal answer.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers