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
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 of the problem is given as n items {1, 2 ... n}. Each item comes with a non-negative value vi and a non-negative and integral size wi. The integrality of the size is essential, as it allows us to use discrete evaluation steps in the dynamic programming algorithm, as it will be shown below. The maximum total integral non-negative size W is also given as input.
The output should be a subset S ⊆ {1, 2 ... n} that maximizes the value of all objects of the subset:
∑vi i∈S
in such a way that they all "fit" within the capacity W:
∑wi ≤ W i∈S
Dynamic Programming Solution Discussion
A dynamic programming solution usually starts with an analysis of the optimal solution and with an attempt to express the optimal solution as a function (recurrence) of smaller solutions. Once the recurrence expression is established, the algorithm proceeds with a "brute force" computation of the smaller solutions and the choosing of the solution at step i based on the previous results. This "brute force" approach is feasible, because the number of smaller solutions is asymptotically small, so it makes sense to compute them in an efficient running time. The third step of the algorithm is executed after the optimal solution is computed, and consists in backtracking the (possibly multidimensional) array of smaller solutions and establishing what input elements are actually part of the solution.