Revision as of 00:12, 28 October 2021

External

The input is given by n items {1, 2 ... n}. Each item comes with a non-negative value v_i and a non-negative and integral size w_i.

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:

 ∑v_i
i∈S

so they all "fit" within the capacity W:

 ∑w_i ≤ W
i∈S

@@ Line 5: / Line 5: @@
 =Overview=
 =Problem Defintion=
-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>.
+The input is given by n items {1, 2 ... n}. 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 ⊆ {i<sub>1</sub>, i<sub>2</sub>, ... i<sub>n</sub>} that maximizes the value of all objects of the subset:
+The output should be a subset S ⊆ {1, 2 ... n} that maximizes the value of all objects of the subset:
 <font size=-1>
    ∑v<sub>i</sub>