We consider a coin-changing problem. For a currency with coins C, C2, ..., CN, the problem...

Transcribed Image Text:

We consider a coin-changing problem. For a currency with coins C₁, C2, ..., CN, the problem is to find the minimum number of coins needed to make x dollars of change, as well as how many coins are needed for each of c, where 1 ≤ i ≤ N, assuming there are always enough coins. For example, in Hong Kong, we have 0.1-dollar, 0.2-dollar, 0.5-dollar, 1-dollar, 2-dollar, 5- dollar and 10-dollar coins. For x = 63.7, the minimum number of coins is 10: 6 x 10-dollar coins, 1x 2-dollar coin, 1 x 1-dollar coin, 1 x 0.5-dollar coin and 1 x 0.2 dollar coin. You can assume x must be a sum of the face value of coins. Write the pseudocode to solve this problem. We consider a coin-changing problem. For a currency with coins C₁, C2, ..., CN, the problem is to find the minimum number of coins needed to make x dollars of change, as well as how many coins are needed for each of c, where 1 ≤ i ≤ N, assuming there are always enough coins. For example, in Hong Kong, we have 0.1-dollar, 0.2-dollar, 0.5-dollar, 1-dollar, 2-dollar, 5- dollar and 10-dollar coins. For x = 63.7, the minimum number of coins is 10: 6 x 10-dollar coins, 1x 2-dollar coin, 1 x 1-dollar coin, 1 x 0.5-dollar coin and 1 x 0.2 dollar coin. You can assume x must be a sum of the face value of coins. Write the pseudocode to solve this problem.

Answer rating: 100% (QA)

You can solve the coinchanging problem using dynamic programming Heres a pseudocode to find the mini... View the full answer