3. (14 pts) Give an efficient algorithm to compute the number of optimal solutions to the Knapsack problem. Recall the Knapsack problem has as its input a list L = [(v1, w1), . . . , (vn, wn)] and a threshold weight W , and the goal is to select a subset S of L maximizing iS vi, subject to the constraint that iS wi W. For this problem, you will count the number of such optimal solutions. Your algorithm should run in O(nW) time. If you only give an inefficient recursive algorithm, you can still receive up to 6 pts. (If you are having trouble solving this problem, you may want to start by developing an inefficient recursive algorithm and then seeing how to improve it using techniques from class.)