Thanks! Consider the problem of \"making change\" in the amount of n cents using

Question

Thanks!

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 collection 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 (1 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. n = _____ (amount of change to make, in cents) Greedy solution: _____ snoldis + _____ snarkis + _____ snooks Optimal solution: _____ snoldis + _____ snarkis + _____ snooks

Explanation / Answer

Let n = 16 cents.

Greedy solution: 1 snoldis + 0 snarkis + 5 snooks

This uses 6 coints total.

But optimal solution is 0 snoldis + 2 snarkis + 0 snooks. Total of 2 coins.

If helpful, do give a thumbs up. For any queries regarding this solution, ask in comments.

----------------

> How do you find your 'n'?

This is a hit and trial method with some intelligent guessing.

Notice that whenever the bigger coin is not the multiple of the smaller coin, greedy solution may not work. This is because if bigger coin is a multiple of smaller coin, then there will never arise a situation, where we can substitue smaller coins to get optimal solution.

If you understand this, then it is easy to see that coins of value 11, 8 and 1 do not follow that property and so greedy method may fail on them. Recall again what was the reason for the condition. Since bigger coin is multiple of smaller coin, we can never get optimal solution by replacing bigger coin by smaller coins right? But in this case, 11 is not a multiple of 8. So, start to find our n, by choosing a multiple of 8 which is greater than 11. First number we get is 16 and it satisfies our answer.

We can also check with 24, 32, 40 etc. However at some point, taking multiples of 11 will beneficial.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.