Today I am continuing on with my review of a book on programming algorithms. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 6 I covered greedy algorithms and dynamic programming. Today I cover the knapsack problem, a well known problem in CS circles.

Let’s say you have a knapsack you want to use for a trip. Your backpack can hold a maximum of twenty pounds, and you want to maximize the value of the items in your knapsack within that twenty pound limit. Your list of possible items looks like this:

item	weight	value
laptop	5 lbs	$1,500
textbook	10 lbs	$100
toiletries	2 lbs	$50
tablet	1 lb	$500
water	8 lbs	$5
blender	5 lbs	$200
dried food	3 lbs	$300

I have made this example a little bit more complicated than the example in the book to make it more challenging to figure out a solution without using the algorithm. The solution involves creating a matrix of the possible combinations of items and figuring out which set of items within the given weight limit has the highest value. So how do we do that?

When you run the code, you will see that all the items except the water fit into the knapsack to get maximum dollar value. That might be the optimal solution for value, but we need water to live. What happens if we make water a required item? Out goes the textbook to make room for it. That adds a wrinkle in the algorithm, but it should be easy enough to add a column to mark required items and force them to be part of any solution.