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.
Carol graduated from Riverside White Cross School of Nursing in Columbus, Ohio and received her diploma as a registered nurse. She attended Bowling Green State University where she received a Bachelor of Arts Degree in History and Literature. She attended the University of Toledo, College of Nursing, and received a Master’s of Nursing Science Degree as an Educator.
She has traveled extensively, is a photographer, and writes on medical issues. Carol has three children RJ, Katherine, and Stephen – one daughter-in-law; Katie – two granddaughters; Isabella Marianna and Zoe Olivia – and one grandson, Alexander Paul. She also shares her life with her husband Gordon Duff, many cats, and two rescues.