Help Please Answer D Thank You So Much 1 (48.27 KiB) Viewed 55 times
Help Please Answer D Thank You So Much 2 (39.35 KiB) Viewed 55 times
Help Please Answer D Thank You So Much 3 (25.5 KiB) Viewed 55 times
= .. Let A = { aj, a2, an} be a finite set of distinct coin types (e.g., a;= 50 cents, az= 25 cents, az= 10 cents etc.). We assume each a; is an integer and that ay > az > ... > 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 integer > 0.
= (b) When a, = 1 a greedy solution to the problem will make change by using the coin types in the order aj, aj, an. When coin type a; is being considered, as many coins of this type as possible will be given. Write an algorithm based on this strategy.
(d) Show that if An = { 28-1, 2--2, ..., 2° } be a set of n distinct coin types then the greedy method in (b) always yields solutions with a minimum number of coins.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!