help Let A = { 11, 8, 5, 1 } be a finite set of coin types. Each type in A is available in unlimited quantity. The coin
Posted: Fri May 20, 2022 3:00 pm
help
Let A = { 11, 8, 5, 1 } be a finite set of coin
types. Each type in A 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 greedy solution to
the problem will make change by using the coin types in the order
of 11, 8, 5, 1. When a coin type is being considered, as many coins
of this type as possible will be given. Give a counterexample to
show that this greedy algorithm doesn't necessarily generate
solutions that use the minimum total number of coins.
Let A = { 11, 8, 5, 1 } be a finite set of coin
types. Each type in A 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 greedy solution to
the problem will make change by using the coin types in the order
of 11, 8, 5, 1. When a coin type is being considered, as many coins
of this type as possible will be given. Give a counterexample to
show that this greedy algorithm doesn't necessarily generate
solutions that use the minimum total number of coins.