... Let An = {a, a2, ..., an} be a finite set of distinct coin types...

 

Transcribed Image Text:

... Let An = {a₁, a2, ..., an} be a finite set of distinct coin types (e.g., a₁= 50 cents, a2= 25 cents, a3= 10 cents etc.). We assume each a; is an integer and that a₁ > a₂ > . > 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. (a) Explain that if a, ‡ 1 then there exists a finite set of coin types and a C for which there is no solution to the coin changing problem. (b) When an = 1 a greedy solution to the problem will make change by using the coin types in the order a₁, a2, ..., 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. (c) Give a counterexample to show that the algorithm in (b) doesn't necessarily generate solutions that use the minimum total number of coins. (d) Show that if An = { k-1, k-2, kº } for some k > 1 then the greedy method in (b) always yields solutions with a minimum number of coins. ... Let An = {a₁, a2, ..., an} be a finite set of distinct coin types (e.g., a₁= 50 cents, a2= 25 cents, a3= 10 cents etc.). We assume each a; is an integer and that a₁ > a₂ > . > 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. (a) Explain that if a, ‡ 1 then there exists a finite set of coin types and a C for which there is no solution to the coin changing problem. (b) When an = 1 a greedy solution to the problem will make change by using the coin types in the order a₁, a2, ..., 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. (c) Give a counterexample to show that the algorithm in (b) doesn't necessarily generate solutions that use the minimum total number of coins. (d) Show that if An = { k-1, k-2, kº } for some k > 1 then the greedy method in (b) always yields solutions with a minimum number of coins.

Answer rating: 100% (QA)

a Explanation If an isnt 1 then there can be certain amounts C for which no combination of the coin types in set An would give a solution For example ... View the full answer