3. Dynamic programming. Consider the 0-1 knapsack problem. You have a knapsack with total capacity W,...

Transcribed Image Text:

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. 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.

Answer rating: 100% (QA)

a The 01 knapsack problem exhibits optimal substructure which mea... View the full answer