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>. | 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 output should be a subset S ⊆ {1, 2, ..., n} that maximizes: | |||
<font size=-1> | |||
∑v<sub>i</sub> | |||
i∈S | |||
</font> | |||
subject to: | |||
<font size=-1> | |||
∑w<sub>i</sub> ≤ W | |||
i∈S | |||
</font> | |||
Revision as of 00:07, 28 October 2021
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:
∑vi i∈S
subject to:
∑wi ≤ W i∈S