The Knapsack Problem: Difference between revisions

From NovaOrdis Knowledge Base
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

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