Question

Greedy Algorithm Design

Answer 1

Answer:

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