Question

(2) Suppose, the game is updated so that every item, i, now has weight, wi], in kilograms (you 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? Can you just greedily select the most valuable items to carry until you run out of capacity? (b) Let V(n, m) denote your maximum total value for any given n, m, v, and w. Give a recursive definition of V: (i) (1 point) Base case int: your base case will occur when m0 since you have no items left to consider. (ii) (4 points) 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)

Please help with question 2 (c).

Answer 1

etue egal to