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. [tex]d_i = b_i - a_i[/tex]
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: [tex]a = [100, 150, 160][/tex]
Then take a list of the hiked price of the items (say list b)
E.g: [tex]b = [110, 180, 165][/tex]
Next, it calculates the difference (d) between corresponding prices [tex]d_i = b_i - a_i[/tex]
[tex]d = [(110 - 100),(180-150),(165-160)][/tex]
[tex]d = [10,30,5][/tex]
Sort the difference from greatest to lowest (as the difference is sorted, lists a and b are also sorted)
[tex]d = [30,10,5][/tex]
[tex]a = [150, 100, 160][/tex]
[tex]b = [180, 110, 165][/tex]
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
[tex]Savings = d[1] + d[2][/tex]
[tex]Savings = 30 +10[/tex]
[tex]Savings = 40[/tex]
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
[tex]a[k] = a[3][/tex]
[tex]a[3] = 160[/tex]
[tex]b[3] = 165[/tex]
Add the saved amount (40) to a[3]
[tex]New\ Amount = 40 + 160[/tex]
[tex]New\ Amount = 200[/tex]
This new amount can then be used to buy b[3] i.e. 165, then they save the change for subsequent items
