Algorithm

I need complete ans for this

4. (20 points) Consider the following variant of 0-1 Knapsack problem, where you have unlimited amount of each of the n items. That is, each item Of has a value and weight wi, and you can take as many copies of O, as you like. Your goal is to take the most valuable goods whose total weight is no more than W. Note that W and each wi is an integer. In the original Knapsack problem, you can take or not take for each item, but bere you can take 0, 1, 2... copies. We now develop a dynamic programming algorithm. In particular, we define M] as the highest value you can pack such that the total weight of the packed items is at most w. a. (pt) How can we find the optimal solution (in the form of the maximum value) from M table? b. (I pt) Write down the initial condition: Mio c. (7 pts) Write down the recurrence for M(w] and briefty explain why it works. d. (7pts) Write down the dynamic programming algorithm. Your algorithm should return the largest dollar amount you can pack (but you do not have to find which items to pack). Note: you need to write down the pseudo-code. Now analyze the running time. Does the algorithm run in polynomial time? e. (4 pts) Justify your