The Knapsack Problem: Difference between revisions
| Line 10: | Line 10: | ||
=Problem Defintion= | =Problem Defintion= | ||
The input is given | The input of the problem is given as 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>. The integral part of the size is essential, as it allows us to use discrete evaluation steps in the dynamic programming algorithm, as it will be shown below. The maximum total size W, which is integral non-negative, is also given as input. | ||
The output should be a subset S ⊆ {1, 2 ... n} 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: | ||
| Line 19: | Line 17: | ||
i∈S | i∈S | ||
</font> | </font> | ||
in such a way that they all "fit" within the capacity W: | |||
<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 22:13, 1 November 2021
External
- https://www.coursera.org/learn/algorithms-greedy/lecture/LIgLJ/the-knapsack-problem
- https://www.coursera.org/learn/algorithms-greedy/lecture/0n68L/a-dynamic-programming-algorithm
- https://www.coursera.org/learn/algorithms-greedy/lecture/LADQc/example-review-optional
Internal
Overview
The knapsack problem shows up every time there's a budget and we want to use it in the most optimal way possible, as a function of a second dimension. This is a quite fundamental problem which is a canonical use for the dynamic programming paradigm.
Problem Defintion
The input of the problem is given as n items {1, 2 ... n}. Each item comes with a non-negative value vi and a non-negative and integral size wi. The integral part of the size is essential, as it allows us to use discrete evaluation steps in the dynamic programming algorithm, as it will be shown below. The maximum total size W, which is integral non-negative, is also given as input.
The output should be a subset S ⊆ {1, 2 ... n} that maximizes the value of all objects of the subset:
∑vi i∈S
in such a way that they all "fit" within the capacity W:
∑wi ≤ W i∈S