Problem 1: Knapsack: which items to take? In class we developed the dynamic programming solution for the knapsack problem, which allows us to compute the value of the optimal solution (OPT) in (nW) time. In this problem you will extend this solution to compute which items the thief should take (a) At first glance we might think that we can compute the optimal solution at the same time as we are computing the optimal value. Consider the following naive modification (underlined code) of the iterative knapsack solution we saw from class, and explain why it does not work. Hint: why can't we start printing items to take until we compute all the way up to MIn, W]? input: item weights W,..., Wn and values V,.., Vn and knapsack capacityW for w 0 to W M[0, w] = 0 for i 1 to n for w = 1 to W if (wi > w) else print i //item i is in optimal solution return MIn, W] (b) Describe how once M is computed, we can generate the list of items that the thief should take What is your algorithm's asymptotic running time? Problem 1: Knapsack: which items to take? In class we developed the dynamic programming solution for the knapsack problem, which allows us to compute the value of the optimal solution (OPT) in (nW) time. In this problem you will extend this solution to compute which items the thief should take (a) At first glance we might think that we can compute the optimal solution at the same time as we are computing the optimal value. Consider the following naive modification (underlined code) of the iterative knapsack solution we saw from class, and explain why it does not work. Hint: why can't we start printing items to take until we compute all the way up to MIn, W]? input: item weights W,..., Wn and values V,.., Vn and knapsack capacityW for w 0 to W M[0, w] = 0 for i 1 to n for w = 1 to W if (wi > w) else print i //item i is in optimal solution return MIn, W] (b) Describe how once M is computed, we can generate the list of items that the thief should take What is your algorithm's asymptotic running time