The Knapsack Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
=External= | =External= | ||
* https://www.coursera.org/learn/algorithms-greedy/lecture/LIgLJ/the-knapsack-problem | * 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 | |||
=Internal= | =Internal= | ||
* [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]] | * [[Algorithms#Dynamic_Programming_Algorithms|Dynamic Programming Algorithms]] | ||
Revision as of 17:42, 28 October 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
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