Q3. [20] The Feasibility Check in Coin Change Problem A clerk often encounters t

Question

Q3. [20] The Feasibility Check in Coin Change Problem A clerk often encounters the problem of given change for a purchase because customers usually don’t want to receive a lot of coins. So, his goal is to minimize the number of coins for a change.

1. [10] Develop a recursive or an iterative greedy algorithm.

2. [5] The coins consist of U.S. coins which are available. The owed amount is 36 cents. What is an optimal solution?

3. [5] Suppose that the new 12-cent U.S. coin is available. The owed amount is 16 cents. What is the optimal solution? Does your algorithm find the optimal solution?

Explanation / Answer

Answer:

1)

1. Whatever coins we have as a alter to give to client, now sort them in growing order of worth

2. Set S= {} empty (set of coins)

3. As (amount) is not zero:

   3.1 pk is largest coin such that x > Pk,

       If rejection such coin exist return "no solution"

       Else:

       x = x - Pk // x cents we have to return

       S = S U { Pk } // add the coin in the alter to give (in set of change)

2)

In 36 cents the best solution determination be 25+10+1= 36 cents (3 coins)

3)

inside this case 4 coins determination is necessary that is 5+5+5+1= 16 (Four Coins),

Except our voracious answer will give five coins as consequence and that determination be 12+1+1+1+1= 16,

That is why we alter to dynamic encoding in which the resolution is optimal as well as time complication is moreover more.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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