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

Question

2. 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.1 (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. [Hint: It may be easier to write a small program than to work this out by hand.] (b) Describe a recursive algorithm that computes, given an integer k, the minimum number of bills needed to make k Dream Dollars. Express your running time using a recurrence relation. You do not need to solve the running time recurrence to get full credit. (And don't worry about making your algorithm fast; just make sure it's correct. We'll learn how to make it fast next week.)

Explanation / Answer

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

Optimal solution: $91 x5

haha! was tough though!

i have answered part a and working on part b.please upvote

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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