Question

Greedy Algorithm Design

A couple wants to buy n major items. They will buy one item per month. They will buy all of their items at the CrazySuperStore. Due to the current economy, it is known that at some point in the future there will be a single price hike on all items at the same time, but due to the uncertainty of economic processes, it is not known when that price hike will occur. For each of the n items the couple wants to buy, both the current price, ai and the future price, bi (bi > ai), are known. (Note that the individual price hikes on items may vary. For example, one item may go from $100 to $105 while another might go from $300 to $400. They only assumption you may make about the prices is that the second price is strictly higher than the first and that you have access to all before/after prices.) Devise a greedy strategy so that the couple is guaranteed to minimize the amount of money they spend on the items. Assume that no matter what, the couple will buy all items. Clearly describe your strategy and intuitively (or formally) prove why it's optimal.

Answer 1

The algorithm is as follows:

1. Start

2. Get the number of items (n)

3. Get the current price of the n items (a1, a2..... an)

4. Get the possible hiked price of the n items (b1, b2..... bn)

5. Calculate the difference between the current and hiked prices for each item i.e.
`d_i = b_i - a_i`

6. Sort the differences in descending order (i.e. from the greatest to the least)

7. Buy items in this order of difference

8. Stop

Explanation:

The algorithm is self-explanatory; however, what it does is that:

It takes a list of the current price of items (say list a)

E.g:
`a = [100, 150, 160]`

Then take a list of the hiked price of the items (say list b)

E.g:
`b = [110, 180, 165]`

Next, it calculates the difference (d) between corresponding prices
`d_i = b_i - a_i`

`d = [(110 - 100),(180-150),(165-160)]`

`d = [10,30,5]`

Sort the difference from greatest to lowest (as the difference is sorted, lists a and b are also sorted)

`d = [30,10,5]`

`a = [150, 100, 160]`

`b = [180, 110, 165]`

If there is no hike up to item k, the couple would have saved (i = 1 to d[k-1])

Assume k = 3

The couple would have saved for 2 item

`Savings = d[1] + d[2]`

`Savings = 30 +10`

`Savings = 40`

The saved amount will then be added to the kth item in list a i.e. a[k](in this case k = 3) in order to buy b[k]

Using the assumed value of k

`a[k] = a[3]`

`a[3] = 160`

`b[3] = 165`

Add the saved amount (40) to a[3]

`New\ Amount = 40 + 160`

`New\ Amount = 200`

This new amount can then be used to buy b[3] i.e. 165, then they save the change for subsequent items