The U.S. treasury recently announced that Harriet Tubman will replace Andrew Jac

Question

The U.S. treasury recently announced that Harriet Tubman will replace Andrew Jackson on the $20 bill. As is usual with such changes, it was not universally popular. TV anchor Greta Van Susteren suggested that we should leave Jackson on the $20 bill and instead create a new $25 bill featuring Tubman. If Van Sustren’s plan were adopted, the U.S. currency would have the following denominations: $1, $2, $5, $10, $20, $25, $50, and $100. With this proposed set of denominations, would the greedy algorithm remain optimal for giving change (or would the U.S. public have to learn more advanced techniques)? Prove your answer correct.

Explanation / Answer

Yes, greedy algorithm will still remain optimal for giving change because the basic principle is at every iteration for search of a coin,take the largest coin which can fit into remaining amount to be changed at that particular time. At the end you will have optimal solution.

But, it won't work if the there is no coin with denomination 1

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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