# Breaking Down The Knapsack Problem

##### July 10, 2020

Imagine you are a world-class thief, and you have just burglarized a house with many valuable artifacts. You have brought a backpack or a knapsack, but it can only contain a limited amount of weight. Your goal is to leave with the highest combined value of items that fit in your bag, but how do you pick these items and what is the optimal value? This is the Knapsack Problem.

For example, let’s say there are five items and the knapsack can hold 20 pounds.

• A signed baseball that weighs 3 pounds and is worth $5,000. • A bottle of wine that weighs 4 pounds and is worth$7,000
• A medieval helmet that weight 5 pounds, worth $5,000 • A painting that weighs 8 pounds and is worth$8,000

## Sources

Kleinberg, J. Tardos, E. (2006). Algorithm Design. Cornell University.