Let A,-{ al, a2, , an } be a finite set of distinct coin types (e.g., ?,-50 cent

Question

Let A,-{ al, a2, , an } be a finite set of distinct coin types (e.g., ?,-50 cents, a2-25 cents, a,- 10 cents etc.). We assume each ai is an integer and that ai > a>> an. Each type is available in unlimited quantity. The coin changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer0. (a) When an a greedy solution to the problem will make change by using the coin types in ., a. When coin type a is being considered, as many coins of this type as the order a, az, possible will be given. Write an algorithm based on this strategy. solutions that use the minimum total number of coins. with a minimum number of coins. (b) Give a counterexample to show that the algorithm in (a) doesn't necessarily generate (c) Show that if Ank1, k"^, k then the greedy method in (a) always yields solutions

Explanation / Answer

// t = number of cents to generate a coin array for

// A[1..n] = Array of coin values

// Returns an array C[1..n] of the number of coins of each value, where

// the sum from 1 to n of C[i]*A[i] will equal t.

Greedy-Coins( t, A )

    Define array C as an array of length n with all values zero

    for i = 1 to n

        C[i] = t / A[i] // Note use INTEGER arithmetic here

        t = C[i] mod A[i] // Note using integer modulo here to get the remainder

    end fo ...ro

    return C

An easy counterexample would be to use V = ( 5, 3, 1 ), and t = 9. The greedy algorithm will return values ( 1, 0, 4), but a little intuition shows that the array ( 0, 3, 0 ) will use fewer coins.

c) If we consider the array A = ( kn-1, kn-2, ..., k0), and k > 0, then we can see that for any k < (n-1), there will be at most (k-1) coins of that value; if there had been sufficient "value" remaining to select k coins o that value, the greedy algorithm would have selected one more coin of the next coin up. Another way to look at this is that for any selection by the greedy algorithm from ki ... k0, the value MUST be less than ki+1, since ki+1 is by definition a multiple of ki.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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