Ryan Avery

Knapsack Problem


The knapsack problem is a popular challenge in computer science that deals with combinatorial optimization. The player is given a knapsack that can carry a certain amount of weight and a selection of items that can be added to that knapsack. Each item has a set value and weight, and it's the goal of the player to optimize the value gained by adding items to the knapsack while not exceeding the maximum weight capacity.

In this assignment for CS-421, Design and Analysis of Algorithms, I was tasked with solvinglarge project picture the knapsack problem in two ways. The first way I solved this problem was with recursion. I made a function that would take an item and determine the maximum possible value that could be obtained by adding the item to the knapsack or not adding the item to the knapsack, and this was done by calling that same function again on the next item that had not yet been checked, and so on. This method would find an optimal solution, however it was not as efficient as the second way that I solved the problem.

The second way that I solved the knapsack problem was with dynamic programming. The way I did this by breaking the problem in to smaller subproblems which were easier and much faster to solve. Once I had solved these subproblems, I saved the answer into a table and then referenced those answer when I began to solve slightly larger subproblems. Eventually, I had a complete table made that I could reference when trying to solve the entire knapsack problem.

The image displayed on this page shows the results I obtained when using my solution to the knapsack problem with a 50 weight knapsack and 17 different items to choose from. On the left of the image, each item is shown with its corresponding weight and value. On the right, you can see first the answer that was obtained using my recursive algorithm. This is an optimal solution, however my recursive function was called 54,160 times in order to find this solution. Below that, however, you can see the solution obtained with my dynamic programming algorithm which also came to the optimal solution however with much less computing power. The total number of times the algorithm referenced the answers stored in the table it created was only 1,572 times.