The Knapsack Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/LIgLJ/the-knapsack-problem
• https://www.coursera.org/learn/algorithms-greedy/lecture/0n68L/a-dynamic-programming-algorithm
• https://www.coursera.org/learn/algorithms-greedy/lecture/LADQc/example-review-optional

Internal

• Dynamic Programming Algorithms

Overview

The knapsack problem shows up every time there's a budget and we want to use it in the most optimal way possible, as a function of a second dimension. This is a quite fundamental problem which is a canonical use for the dynamic programming paradigm.

Problem Defintion

The input is given by n items {1, 2 ... n}. 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 W:

 ∑wi ≤ W
i∈S