[12 marks] Dynamic programming In the NUGGETSINSWAMP problem, the input is an array W of n...

Transcribed Image Text:

[12 marks] Dynamic programming In the NUGGETSINSWAMP problem, the input is an array W of n positive integers W[1], ..., W[n] representing the weights of nuggets lying on your path in a swamp. You would like to pick up some of the nuggets maximizing the total weight (which is your profit). Bad news is - you cannot pick up two adjacent nuggets. The valid solution for this problem is the largest possible weight of nuggets that can be obtained by picking up a subset of the entries of W such that the subset contains at most one of any two consecutive entries W[i], W[i+1] for every 1 ≤ i ≤ n - 1. For example, given array W=[4,6,7,1,5], the maximum weight that satisfies constraints is W[1] + W[3] + W[5] = 4 + 7 + 5 = 16, while W[2] + W[3] + W[5] = 6 + 7 + 5 = 18 does not satisfy constraints as it picks two consecutive entries W[2], W[3]. In this question, you will design and analyze a dynamic programming algorithm that solves the NUGGETSINSWAMP problem. (a) Provide an example of input to show that in some cases, the optimal solution can skip two consecutive entries in the array. (b) Give an example of input to show that the greedy algorithm of choosing the entries in order of decreasing weight (from largest to smallest while satisfying constrains) does not always give the best solution. (c) Give a precise definition of a subproblem that can be used to solve the NUGGETSINSWAMP problem with a dynamic programming algorithm. What is the quantity associated with this subproblem? [12 marks] Dynamic programming In the NUGGETSINSWAMP problem, the input is an array W of n positive integers W[1], ..., W[n] representing the weights of nuggets lying on your path in a swamp. You would like to pick up some of the nuggets maximizing the total weight (which is your profit). Bad news is - you cannot pick up two adjacent nuggets. The valid solution for this problem is the largest possible weight of nuggets that can be obtained by picking up a subset of the entries of W such that the subset contains at most one of any two consecutive entries W[i], W[i+1] for every 1 ≤ i ≤ n - 1. For example, given array W=[4,6,7,1,5], the maximum weight that satisfies constraints is W[1] + W[3] + W[5] = 4 + 7 + 5 = 16, while W[2] + W[3] + W[5] = 6 + 7 + 5 = 18 does not satisfy constraints as it picks two consecutive entries W[2], W[3]. In this question, you will design and analyze a dynamic programming algorithm that solves the NUGGETSINSWAMP problem. (a) Provide an example of input to show that in some cases, the optimal solution can skip two consecutive entries in the array. (b) Give an example of input to show that the greedy algorithm of choosing the entries in order of decreasing weight (from largest to smallest while satisfying constrains) does not always give the best solution. (c) Give a precise definition of a subproblem that can be used to solve the NUGGETSINSWAMP problem with a dynamic programming algorithm. What is the quantity associated with this subproblem?

Answer rating: 100% (QA)

a Input W10 5 8 1 7 6 Optimal solution W1 W4 W6 10 7 6 23 This optimal solution skips two consecutive entries W2 and W3 in the array Algorithm NUGGETS... View the full answer