How the Mathematical Conundrum Called the ‘Knapsack Problem’ Is All Around Us
by Elizabeth Landau/Smithsonianmag.com
Imagine you’re a thief robbing a museum exhibit of tantalizing jewelry, geodes, and rare gems. You’re new at this, so you only brought a single backpack. Your goal should be to get away with the most valuable objects without overloading your bag until it breaks or becomes too heavy to carry. How do you choose among the objects to maximize your loot?
You could list all the artifacts and their weights to work out the answer by hand. But the more objects there are, the more taxing this calculation becomes for a person—or a computer.
This fictional dilemma, the “knapsack problem,” belongs to a class of mathematical problems famous for pushing the limits of computing. And the knapsack problem is more than a thought experiment. “A lot of problems we face in life, be it business, finance, including logistics, container ship loading, aircraft loading — these are all knapsack problems,” says Carsten Murawski, professor at the University of Melbourne in Australia. “From a practical perspective, the knapsack problem is ubiquitous in everyday life.”
Researchers once took advantage of the problem’s complexity to create computer security systems, but these can now be cracked since the problem has been so well studied.