> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/dynamic_programming/knapsack_problem.md).

# Knapsack Problem

Each item contains a weight and a value. A knapsack contains a finite capacity.

* **Goal**: maximize the values in the knapsack while not overloading the capacity.
* O/1 means we can either put items in the knapsack, or we do cannot. No splitting of items is allowed.

Base Conditions

* 0 weight = 0 items (cannot fit anything).
* 0 items = 0 knapsack items.