Description
The Knapsack Problem is a well known NP-hard problem. This means that no polynomialtime (PT) algorithm is known to solve this problem. Many computer scientists believe that a PT algorithm cannot be found to solve Knapsack, although this hypothesis has not been proven.
For this project, you will explore three ways to solve one instance of the knapsack problem, and compare time and space efficiencies for them. Here is the sample knapsack that has the capacity to carry 6 pounds:
Item Weight Value 1 3 25 2 2 20 3 1 15 4 4 40 5 5 50
Please write and test Python code for the following three different solution types:
1. Exhaustive Search – try all possibilities
2. Dynamic Programming (DP) Method – as discussed in class
3. Your Method of Choice – Do some research and choose another method. This method must perform better or the same as your DP method.
Although you are given this small example, your code should be able to input a size n matrix of weights and values and a knapsack size (read in a file). Here are the steps to complete the project: • Step 1. Code an exhaustive search algorithm to find the optimal solution to the above problem.
2
• Step 2. Code a DP method to find the optimal solution to the problem. • Step 3. Code your chosen method to find the optimal solution to the problem. • Step 4. Be sure to create a user friendly menu (no crashing and easy exit, read knapsack data from a file). • Step 5. Answer the following questions: 1. What is the time/space efficiency of each of your algorithms? 2. Do all three of your solutions provide an optimal solution? Why or Why not? 3. Create and supply two other knapsack examples to test your 3 functions. 4. Which is the better knapsack solution and why? Is this true for all knapsack examples? • Step 6. Write your professional report that includes an executive summary and answers the above questions.
