3. Dynamic programming. Consider the 0-1 knapsack problem. You have a knapsack with total capacity W, and n distinct items with values V, V2, ..., Un and weights w, W2, ..., Wn. You can either choose to add one item to your knapsack or leave it. The goal is to maximize the value of the items in the knapsack without exceeding its capacity. Answer the questions below. (a) Prove that it has optimal substructure (hint: consider the solutions to all sub-problems in which item i, with weight w, has been removed). (b) Based on the optimal substructure, give a recursion to solve the problem. (c) Show an example of the optimal substructure given the input below for W = 10 (clearly indicate the solution to the overall problem and the solutions to sub-problems) i 1 2 3 4 Wi Vi 6 30 3 14 4 16 2 9 (d) Show the overlapping sub-problems as you recursively solve the problem for the input above (i.e., draw the recursion tree in which each node corresponds to the size of the knapsack for the corresponding sub-problem). Give an algorithm to solve the problem (write pseudo-code). (f) Solve the problem instance above using your algorithm (show the completed dynamic program- ming table).. (g) Give the running time of your algorithm.