5. Dynamic programming (20 points) Let's say that you have n identical pieces of candy that you want to sell for as much

[answerhappygod]

5 Dynamic Programming 20 Points Let S Say That You Have N Identical Pieces Of Candy That You Want To Sell For As Much 1 (61.1 KiB) Viewed 64 times

5. Dynamic programming (20 points) Let's say that you have n identical pieces of candy that you want to sell for as much as possible. Oddly, you can sometimes make more by selling a subset together, rather than as individual pieces. You are given a table that says for each O<i<= n how much profit you can achieve for a set of i pieces of candy. For i pieces, your profit is pi. Note that selling a set with i pieces of candy does not prevent you from selling another set with the same number of candies for the same price (if you still have enough left). Your goal is to develop an algorithm that maximizes the profit of selling all of the candy by determining the highest value division of the n pieces. (a) Give a recurrence relation that expresses the optimal value that can be obtained. (b) Give an efficient algorithm (with respect to both time and space) for computing the maximum value that can be achieved. (c) What is the running time of your algorithm in Big-Theta notation? How much memory is required?