In a previous life, you worked as a cashier in the lost Antarctican colony of Na

Question

In a previous life, you worked as a cashier in the lost Antarctican colony of Nadira, spending the better part of your day giving change to your customers. Because paper is a very rare and valuable resource in Antarctica, cashiers were required by law to use the fewest bills possible whenever they gave change. Thanks to the numerological predilections of one of its founders, the currency of Nadira, called Dream Dollars, was available in the following denominations: $1, $4, $7, $13, $28, $52, $91, $365. (a) The greedy change algorithm repeatedly takes the largest bill that does not exceed the target amount. For example, to make $122 using the greedy algorithm, we first take a $91 bill, then a $28 bill, and finally three $1 bills. Give an example where this greedy algorithm uses more Dream Dollar bills than the minimum possible.

Explanation / Answer

Example :
Amount = $455
Greedy solution: $365 + $52 + $28 + $7 + $1 + $1 + $1

Optimal solution: $91 x5

haha! was tough though!

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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