The Knapsack Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
=Problem Defintion= | =Problem Defintion= | ||
The input is given by n items. Each item comes with a non-negative value v<sub>i</sub> and a non-negative and integral size w<sub>i</sub>. Additionally, a non-negative integral capacity W is also given. | The input is given by n items {i<sub>1</sub>, i<sub>2</sub>, ... i<sub>n</sub>}. Each item comes with a non-negative value v<sub>i</sub> and a non-negative and integral size w<sub>i</sub>. Additionally, a non-negative integral capacity W is also given. | ||
The output should be a subset S ⊆ {1, 2, ... | The output should be a subset S ⊆ {i<sub>1</sub>, i<sub>2</sub>, ... i<sub>n</sub>} that maximizes the value of all objects of the subset: | ||
<font size=-1> | <font size=-1> | ||
∑v<sub>i</sub> | ∑v<sub>i</sub> | ||
Revision as of 00:09, 28 October 2021
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:
∑wi ≤ W i∈S