The Knapsack Problem

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

External

Internal

Overview

Problem Defintion

The input is given by n items. Each item comes with a non-negative value vi and a non-negative and integral size wi. 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