The Knapsack Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
* [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]] | * [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]] | ||
=Overview= | =Overview= | ||
The knapsack problem shows up every time there's a budget and we want to use it in the most optimal way possible. | |||
=Problem Defintion= | =Problem Defintion= | ||
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>. | 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>. | ||
Revision as of 17:03, 28 October 2021
External
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.
Problem Defintion
The input is given by n items {1, 2 ... n}. 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 W:
∑wi ≤ W i∈S