Consider a country whose coins come in k different denominations. Let these coin

Question

Consider a country whose coins come in k different denominations. Let these coins have values d1 < d2 < ··· < dk cents.

(a) Give a dynamic programming algorithm that determines the fewest number of coins needed to add up to a total value of n cents.1 What is the running time of your dynamic program?

(b) The greedy algorithm for money changing is the following. Let n be the target value. Select a coin di of greatest value that is at most n; recurse on n di. Give an example to show that the greedy algorithm does not always produce an optimal answer.

Explanation / Answer

Answer for Question 1:

See this below method implementation for getting optimal solution to get the minimum number of coins to get the requirement..
with understandable format using basic programming logics.

// m is size of coins array (number of different coins)
int minCoins(int coins[], int m, int V)
{
// base case
if (V == 0) return 0;

// Initialize result
int res = INT_MAX;

// Try every coin that has smaller value than V
for (int i=0; i<m; i++)
{
if (coins[i] <= V)
{
int sub_res = minCoins(coins, m, V-coins[i]);

// Check for INT_MAX to avoid overflow and see if
// result can minimized
if (sub_res != INT_MAX && sub_res + 1 < res)
res = sub_res + 1;
}
}
return res;
}

Answer for Question 2:

A simple example is the set of denominations without the nickel. If
you simply have the values {1, 10, 25}, the greedy solution will fail. For example,
if you are trying to make change for 30 cents, the greedy solution will first take a
quarter, followed by 5 pennies, a total of six coins. However, the optimal solution
actually consists of three dimes.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.