Algorithms For Dummies

Looking inside the knapsack

The knapsack problem has been around since at least 1897 and is likely the work 

of Tobias Dantzig (

https://www.britannica.com/biography/Tobias-Dantzig

). 

In this case, you have to pack up your knapsack with as many items as possible. 

Each item has a value, so you want maximize the total value of the items you 

carry. The knapsack has a threshold capacity or you have a limit of weight you can 

carry, so you can’t carry all the items.

The general situation fits any problem that involves a budget and resources, and 

you want to allocate them in the smartest way possible. This problem setting is so 

common that many people consider the knapsack problem to be one of the most 

popular algorithmic problems. The knapsack problem finds applications in com-

puter science, manufacturing, finance, logistics, and cryptography. For instance, 

real-world applications of the knapsack problem are how to best load a cargo ship 

with goods or how to optimally cut raw materials, thus creating the least waste 

possible.

Even though it’s such a popular problem, this book doesn’t explore the knapsack 

problem again because the dynamic approach is incontestably one of the best 

solving approaches. It’s important to remember, though, that in specific cases, for 

such as when the items are quantities, other approaches, such as using greedy 

algorithms, may work equally well (or even better).

---

CHAPTER 16