The Knapsack Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 7: | Line 7: | ||
* [[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, as a function of a second dimension. This is a quite fundamental problem. | 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 [[Algorithms#Dynamic_Programming_Algorithms|dynamic programming paradigm]]. | ||
=Problem Defintion= | =Problem Defintion= | ||
Revision as of 22:10, 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 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