View source for Knapsack problem

The '''knapsack problem''' or '''rucksack problem''' is a problem in [[combinatorial optimization]]: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

== Description ==

It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

The problem often arises in resource allocation where there are financial constraints and is studied in fields such as [[combinatorics]], [[computer science]], [[complexity theory]], [[cryptography]], [[applied mathematics,]] and daily fantasy sports.

The knapsack problem has been studied for more than a century, with early works dating as far back as 1897.

The name "knapsack problem" dates back to the early works of mathematician [[Tobias Dantzig ]](1884–1956), and refers to the commonplace problem of packing your most valuable or useful items without overloading your luggage.

== See also ==

* [[Change-making problem]]
* [[Combinatorial auction]]
* [[Combinatorial optimization]]
* [[Continuous knapsack problem]]
* [[Cutting stock problem]]
* [[List of knapsack problems]]
* [[Packing problem]]

== External links ==

* [https://en.wikipedia.org/wiki/Knapsack_problem Knapsack problem] @ Wikipedia



[[Category:Mathematics]]