The Knapsack Problem

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

External

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