In problems 5 and 6, consider the problem of money investment. Suppose there are m different...

 

Transcribed Image Text:

In problems 5 and 6, consider the problem of money investment. Suppose there are m different money investment plans P1, P2,..., Pm available. Plan P; takes y; years and will increase your money by a factor of (1+r). (In other words, if you invest D dollars in plan P, after y, years, you will have D(1+r) dollars.) For every i, y, is a positive integer and r; 0. You start with some fixed amount of money M and need to choose a series of plans to invest one by one. You must invest all your money into a single plan at any given time. Your must select some plans with the total duration at most n years. The goal is to maximize your money at the end of these investments. The series of plans you choose may include the same plan any number of times. Assume that the annual interest rate r; satisfies r1 r2 >> rm. Problem 5 (15%) Consider the greedy algorithm which picks plan P, repeatedly until the next P does not fit into n years, then pick P2 repeatedly until the next P2 does not fit, and so on. 1. (5%) Find an example in which the greedy algorithm does not find the optimal solution. 2. (10%) Assume that y, is a multiple of y+1 for i=1,2,..., m-1. Prove that the greedy algorithm always returns the optimal solution in this case. In problems 5 and 6, consider the problem of money investment. Suppose there are m different money investment plans P1, P2,..., Pm available. Plan P; takes y; years and will increase your money by a factor of (1+r). (In other words, if you invest D dollars in plan P, after y, years, you will have D(1+r) dollars.) For every i, y, is a positive integer and r; 0. You start with some fixed amount of money M and need to choose a series of plans to invest one by one. You must invest all your money into a single plan at any given time. Your must select some plans with the total duration at most n years. The goal is to maximize your money at the end of these investments. The series of plans you choose may include the same plan any number of times. Assume that the annual interest rate r; satisfies r1 r2 >> rm. Problem 5 (15%) Consider the greedy algorithm which picks plan P, repeatedly until the next P does not fit into n years, then pick P2 repeatedly until the next P2 does not fit, and so on. 1. (5%) Find an example in which the greedy algorithm does not find the optimal solution. 2. (10%) Assume that y, is a multiple of y+1 for i=1,2,..., m-1. Prove that the greedy algorithm always returns the optimal solution in this case.