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.


ATTENTION READERS
Due to the nature of independent content, VT cannot guarantee content validity.
We ask you to Read Our Content Policy so a clear comprehension of VT's independent non-censored media is understood and given its proper place in the world of news, opinion and media.

All content is owned by author exclusively. Expressed opinions are NOT necessarily the views of VT, other authors, affiliates, advertisers, sponsors, partners or technicians. Some content may be satirical in nature. All images within are full responsibility of author and NOT VT.

About VT - Read Full Policy Notice - Comment Policy