Please assist with the problem shown in the given picture: Please assist with th

Question

Please assist with the problem shown in the given picture: Please assist with the problem shown in the given picture: Please assist with the problem shown in the given picture: Please assist with the problem shown in the given picture: Consider the problem of "making change" in the amount of n cents using the fewest possible number of coins. If the only coins that may be used are quarters (25 cents) , dimes (10 cents), nickels (5 cents) and pennies (1 cent), then the "greedy" algorithm described in class- repeatedly adding to the on of coins comprising the "change" the largest-denomination coin whose value is less than or equal to the amount of change remaining to be made - is guaranteed to achieve an optimal solution (that is, to yield the exact amount of change required while using the smallest possible total number of coins). In the Republic of Snoldova, however, the only coin denominations are the snoldi (11 cents), the snarki (8 cents), and the snook (I cent). In the box below, demonstrate that for the Snoldovan system of coinage the greedy algorithm described above does not always give an optimal solution to the "making change" problem. Give a value of n (the amount of change required, in cents), the corresponding solution produced by the greedy algorithm above, and a different solution consisting of fewer coins than are used in the greedy algorithm s solution. (amount of change to make, in cents) Greedy solution:-snoldis+ snarkis+ snooks sna Optimal solution:snoldis+ snarkis + snooks

Explanation / Answer

Solution:

The greedy algorithm will fail when n= 27

because it will choose the denomination as

11, 11, 1, 1, 1, 1, 1

which is total of 6 coins

Greedy solution: 2 snoldis + 0 snarkis + 5 snooks

but

the optimal solution is:

11, 8, 8

which is total of three coins

Optimal solution: 1 snoldis + 2 snarkis + 0 snooks

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---