This is coin change problem. Our goal is to use least amount of coin, assuming u

Question

This is coin change problem. Our goal is to use least amount of coin, assuming unlimited supply of coins

a) The set of coin inclue half dollar, quarter, dime nickel, and peny. Can you always reach the goal qith greedy approach? If not, give an example.

b) The set of coins include half dollar, quarter, 12-cent coin, dime, nickel, and penny. CAn you always reach the goal with greedy apprach?if not, give an counter example.

help please it's urgent

Answer any six of the following nine problems. You may work on more problems for extra credit. you must clearly mark the extra credit problem[s] since regular and extra credit problems are graded differently.

Explanation / Answer

a) Yes ,We can reach the goal with greedy algorithm.As greedy algorithm works on the logic that at every stage it chooses the largest coin without worrying about the consequences.

Coins available are:

Greedy Algorithm is defined below:

Make change for n units using the least possible number of coins.

MAKE-CHANGE (n)
        C ? {50, 25, 10, 5, 1}     // constant.
        Sol ? {};                         // set that will hold the solution set.
        Sum ? 0 sum of item in solution set
        WHILE sum not = n
            x = largest item in set C such that sum + x ? n
            IF no such item THEN
                RETURN    "No Solution"
            S ? S {value of x}
            sum ? sum + x
        RETURN S

For example :

Make a change for 2.89 (289 cents) here n = 2.89 and the solution contains 5 half dollars, 1 quarters, 1 dime and 4 pennies. The algorithm is greedy because at every stage it chooses the largest coin without worrying about the consequences. Moreover, it never changes its mind in the sense that once a coin has been included in the solution set, it remains there.

b) Yes , we can reach goal with greedy approach in this scenario also.

For example:

We want change for $2.73(273 cents).

Available coins:

half dollar=50 cents

quarter=25 cents

12-cent coin=12 cents

dime=10 cents

nickel=5

penny=1

So, the solution will contains 5 half dollars, 1 12-cent coin, 1 dime and 1 pennies according to the greedy approach.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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