Help Please answer (d) thank you so much.
Posted: Mon May 02, 2022 11:45 am
Help Please answer (d) thank you so
much.
= .. 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.
much.
- Help Please Answer D Thank You So Much 1 (48.27 KiB) Viewed 56 times
- Help Please Answer D Thank You So Much 2 (39.35 KiB) Viewed 56 times
- Help Please Answer D Thank You So Much 3 (25.5 KiB) Viewed 56 times
= (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.