4. (20 points) Let An = { ai, a, , an } be a finite set of distinct coin types (

Question

4. (20 points) Let An = { ai, a, , an } be a finite set of distinct coin types (e.g., a,-50 cents, a?25 cents, a,- 10 cents etc.). We assume each a is an integer and that a>a2>. > 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 integer> 0. a) When an 1 a greedy solution to the problem will make change by using the coin types irn , an. When coin type a, is being considered, as many coins of this type as (a) doesnt necessarily generate then the greedy method in (a) always yields solutions the order al, a2, 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 (c) Show that if A-k, ka2, k

Explanation / Answer

Hello Student!

a) Greedy approach :

Given : An = {a1, a2, .... , an} be a finite distinct coin types array.

Approach : We will subtract the largest coin available from the given sum and then we will remove the sum with the further coins for example we have {25, 10, 5, 2, 1} and the given sum is 102. The minimum number of coins will be 25x4 and 2x1. This gives us the minimal output.

Algorithm :

greedy_CoinChange( A[], sum )

sort ( A.start , A.end ) ; // sort them in decreasing order // It is already in the ques

coins = 0

for i = 0 ; i < A.end ; i++

if sum >= A[i]

coins = coins + floor(sum/A[i]);

sum = sum - floor(sum/A[i])*A[i];

end

return coins;

(b) The above greedy algorithm will not work for all the cases. Why?

For ex : Let us consider A9 = {9, 6, 5, 1} and the sum we want is 11

If we go through this approach we wil get - {9, 1, 1} but the possible answer would be {6, 5}. Therefore, greedy approach fails for this situation.

(c) An = {kn-1, kn-2, .... , k0} then the greedy algorithm will alwats produce an optimal solution

For k = 3 and n = 5

A5 = {81, 27, 9, 3, 1}

And, if we want a sum of 100

Answer would be {81x1, 9x2, 1x1}

The exponential solution of this equation will always tends to give an optimal solution because, it will form a canonical form. This makes coins to expand exponentially thereby, reducing the main value as much as possible. Therefore, this structure will allow it to effictively ignore possible ways of getting the goal value. Therefore, a coin system with a power of k would allow it to formulate an effective approach with lesser time complexity.

Thank you. Feel free to ask anything. Please upvote, if you like the answer. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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