Python Knapsack Problem

Problem 1: 0-1Knapsack: Recursive vs DP

Given weights and values of n items, select items to place in a knapsack of capacity W to maximize the total value in the knapsack. That is, given two integer arrays val[] and wt[ ] which represent values and weights associated with n items respectively and an integer W which represents knapsack capacity, determine the maximum value subset of val[] such that sum of the weights of this subset is W. Items cannot be broken or used more than once, you either select the complete item or dont select it. Implement both a recursive and dynamic programming algorithm to solve the 0-1 knapsack problem. Both algorithms should return the maximum total value of items that can fit in the knapsack.

a) Give a verbal description and detailed pseudo-code for each algorithm.

b) Implement both algorithms in one program named knapsack. Your program should randomly generate test cases that are solved using both the DP and Recursive algorithm. The program should output to the terminal: n, W, time for the DP algorithm, max for the DP, time for the Recursive algorithm, max for Recursive. The max values should be the same. Sample output is below

c) Conduct experiments to collect running times for randomly generated input. Since there are two variables n and W, you can hold one constant while varying the other and vis-a-versa. This may result in several graphs. Plot the data and fit curves.

d) If the recursive algorithm is too slow you can collect data using different values of W and n. Discuss your implementation, results and how you collected the data. How does W change the running time?

N=10 W =100 N=15 W =100 N=20 W =100 N=25 W =100 N=30 W=100 N=35 W =100 N=40 W =100 Rec time = 0.0122 DP time = 0.0103 max Rec = 478 max DP = 478 Rec time = 0.1752 DP time = 0.0145 max Rec = 676 max DP = 676 Rec time = 2.4546 DP time = 0.0201 max Rec = 739 max DP = 739 Rec time = 16.0216 DP time = 0.0279 max Rec = 617 max DP = 617 Rec time = 192.209 DP time = 0.0323 max Rec = 721 max DP = 721 Rec time = 1891.7 DP time = 0.0354 max Rec = 970 max DP = 970 Rec time = 3782.96 DP time = 0.0416 max Rec = 740 max DP = 740