Suppose you have are working as a cashier in a country that uses different denom

Question

Suppose you have are working as a cashier in a country that uses different denominations of coins than we are used to in the US (1, 5, 10, and 25). Your task is to design an efficient algorithm that will solve the problem of finding the smallest number of coins required to make change. Your algorithm will take the following as input: . denom: an array containing the denominations of all coins d: the number of different denominations ·n: a number of cents to make change for You may assume that the smallest denomination of coin is one, so there is always some way to make change for every n. Note, the naïve strategy of choosing the highest value denomination does not always produce the fewest number of coins. For instance, in a country with 1-, 4-, and 6-cent coins, we can make 9 cents using three coins (4+4+1), which is better than the four coins you would get when using a 6-cent coin (6+1+1+1) Hint: try selecting each denomination of coin in turn, then form change for the remaining cents. For example, when n 9 and denom1,4,6), you could make 9 cents by adding a one-cent coin to the coins that add up to 8 cents, a four-cent coin to coins that add up to 5 cents, or a six-cent coin to coins that add up to 3 cents. In particular, if C(n) represents fewest number of coins needed to make n cents, C(9) = 1 + min(C(8),C(5), C(3)) in this case We can apply the same strategy to any number and denomination coins, yielding the recurrence C(n) 1tdminCn-denomi)), denomi

Explanation / Answer

Assuming we want to make change for n cents and we have infinite supply of each of denom = { S1, S2, .. , Sd} valued coins

The Algorithm makes use of Dynamic Programming strategy:

1. Determining the optimal substructure

2. Overlapping Subproblems

Various subproblems are called again-and-again, and so this problem has overlapping subproblems property.

Following is the dynamic programming code for the solution:

#include<stdio.h>

int count( int denom[], int d, int n )

{

int i, j, x, y;

// We need n+1 rows as the table is consturcted in bottom up manner using

// the base case 0 value case (n = 0)

int table[n+1][d];

  

// Fill the enteries for 0 value case (n = 0)

for (i=0; i<d; i++)

table[0][i] = 1;

// Fill rest of the table enteries in bottom up manner  

for (i = 1; i < n+1; i++)

{

for (j = 0; j < d; j++)

{

// Count of solutions including S[j]

x = (i-denom[j] >= 0)? table[i - denom[j]][j]: 0;

// Count of solutions excluding S[j]

y = (j >= 1)? table[i][j-1]: 0;

// total count

table[i][j] = x + y;

}

}

return table[n][d-1];

}

// Driver program to test above function

int main()

{

int denom[] = {1, 2, 3};

int d = sizeof(denom)/sizeof(denom[0]);

int n = 4;

printf(" %d ", count(denom, d, n));

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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