2. Inventory Management (7 points Suppose you are playing a video game. In this game you can only carry a limited amount of items. Every item has a value and your goal is to maximize the total value of items you are carrying Specifically, you are choosing which of m items to carry where item number i has value vfi (for your recurrence/pseudo-code you can assume you are passed the item values in an array, v, of size m (1) Suppose you can only carry n items of the m available. (a) (1 point) Example: Let n = 3, m = 5. If the item values are u = {5, 30, 17, 32, 40} which 3 should you choose to carry? (b) (1 point) Give a short description of a greedy algorithm which maximizes your total value for any given n.m, and v. (2) Suppose, the game is updated so that every item, i, now has weight, w[i], in kilogranm ou can assume you are passed the item weights in an array, w, of size m). You can only carry n kilograms of weight. (a) (1 point) Example: Let n = 15, m = 5. If the item values are v = {5, 30, 17, 32, 40} and the item weights are w = {2.4.3.6, 15) which should you choose to carry? Which would your greedy algorithm choose to carry? (b) (2 points) Let V(n, m) denote your maximum total value for any given n, m, v, and v. Give a recursive definition of V: i) Base case 0 since you have no items left to Hint: your base case will occur when m consider) (ii) Recursive case (Hint: compare the total value obtained from taking the mth item to the total value obtained from not taking the mth item (c) (2 points) Based on your recurrence, write the pseudo-code for a dynamic pro- gramming algorithm to compute the maximum total value (you can use bottom up dynamic programming or memoization)