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.
