From the lecture, you know how to use dynamic programming to solve the 0-1 knapsack problem where each item is unique and only one of each kind is available. Now let us consider knapsack problem where you have in- finitely many items of each kind. Namely, there are n different types of items. All the items of the same type i have equal size wi and value vi. You are offered infinitely many items of each type. Design a dynamic programming algorithm to compute the optimal value you can get from a knapsack with capacity W. a. Define (in plain English) subproblems to be solved. b. Write a recurrence relation for the subproblems c. Using the recurrence formula in part b, write pseudocode to find the solution. d. Make sure you specify i. base cases and their values ii. where the final answer can be found e. What is the complexity of your solution