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 {i1, i2, ... in}. 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 ⊆ {i1, i2, ... in} 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