The Knapsack Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/LIgLJ/the-knapsack-problem

Internal

• Dynamic Programming Algorithms

Problem Defintion

The input is given by n items. Each item comes with a non-negative value v_i and a non-negative and integral size w_i. Additionally, a non-negative integral capacity W is also given.

The output should be a subset S ⊆ {1, 2, ..., n} that maximizes the value of all objects of the subset:

 ∑vi
i∈S

so they all "fit" within the capacity:

 ∑wi ≤ W
i∈S