1. You are working as a cashier in a country that uses different denominations o

Question

1. You 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). Design an efficient, dynamic programming, algorithm that will solve the problem of finding the smallest number of coins required to make change. You must write pseudo-code for both a memoized version, AND, an iterative version. Your algorithm will take the following as input: . denom: an array containing the denominations of all coins . d: the number of different denominations n: the 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. Hint: try selecting each denomination of coin in turn, then form change for the remaining cents. For example, when n-9 and denom-f1, 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, C(n) represents the fewest number of coins needed to make n cents, C(9) = 1+minJC(8), C(5), C(3), in this case. We can apply the same strategy to any number and denominations of coins giving us the recurrence: C(n)-1 + min(C(n-denom[i]}), denom [i] n

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 1
• Subjects

---

---

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