Question
1. You need to buy a set of n essential items. Cashflow being low but regular, you have also decided to buy one item per day for the next n days (starting tomorrow) Each item i has a current price P, which is the price of that item today. However, all items have prices that change in a linear fashion with slope s,, so that on day j, item i will cost p+s j (where today will be day 0, so items are bought on days 1 through n). Some slopes may be negative, but we must still buy one item per day for the next n days. Do not worry about prices becoming negative. We can assume that all p, and s, values are distinct We want to find the order of item purchases that minimises the total cost of the items; so we want to find a permutation of 1,2,..., n, given by o,2, . .., On (where item i is bought on day o) that minimises i-1 (a) One potential greedy approach would be to buy the currently most expensive item first, and continue in descending order of p Give a counterexample and demonstrate why this approach will not always work. (b) Design and write a greedy algorithm that will always find the smallest total cost Analyse the running time of your al gorithm. (c) Prove that your algorithm from part (b) is correct
Explanation / Answer
(a)
If we buy currently expensive item then in future it value may go down and we can come with higher value.
(b)
Instead of getting higher values we can go with minimum value at a time as there value can go down.
by this way we can minimize the outcome.
(c)
as slope values can be negative so in future days the price will go down as we are subtracting Si.j (on j day) from item price on ith day.
So we will take smallest values first and on each day get the smallest values.
