The Knapsack Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
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. 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: | The output should be a subset S ⊆ {1, 2, ..., n} that maximizes the value of all objects of the subset: | ||
<font size=-1> | <font size=-1> | ||
∑v<sub>i</sub> | ∑v<sub>i</sub> | ||
i∈S | i∈S | ||
</font> | </font> | ||
so they all "fit" within the capacity: | |||
<font size=-1> | <font size=-1> | ||
∑w<sub>i</sub> ≤ W | ∑w<sub>i</sub> ≤ W | ||
i∈S | i∈S | ||
</font> | </font> | ||
Revision as of 00:08, 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 the value of all objects of the subset:
∑vi i∈S
so they all "fit" within the capacity:
∑wi ≤ W i∈S