Think of the familiar situation of packing for a long trip. There are many items that you would like to take with you, but you are limited by the capacity of your suitcase. In your mind, each item has a certain value it will add to your trip; at the same time, each has a size (and weight) associated with it, and each will compete with other items over the available space in your suitcase. This situation is just one of many real-life examples of the knapsack problem, which is considered one of the oldest and most investigated combinatorial search problems.
More formally, the knapsack problem consists of the following components:
- A set of items, each of them associated with a certain value and a certain weight
- A bag/sack/container (the knapsack) of a certain weight capacity
Our goal is to come up with a group of selected items that will provide the...
