8-7. In the United States, coins are minted with denominations of 1, 5, 10, 25,

Question

8-7. In the United States, coins are minted with denominations of 1, 5, 10, 25, and 50 cents. Now consider a country whose coins are minted with denominations of (di, ,dkl units. We want to count how many distinct ways C(n) there are to make change of n units. For example, in a country whose denominations are { 1.6, 10), C(5) = 1, C(6) to C(9) = 2, C(10) = 3, and C(12) = 4. 1. How many ways are there to make change of 20 units from 1,6, 10]? 2. Give an efficient algorithm to compute C(n), and analyze its complexity. (Hint: think in terms of computing C(n, d), the number of ways to make change of n units with highest denomination d. Be careful to avoid overcounting.)

Explanation / Answer

It is Dynamic Programming Problem.

For example, for N = 20 and C = {1,6,10}, there are four solutions: {10,10},{10,6,1,1,1,1},{10,1,1,1,1,1,1,1,1,1,1,1},{6,6,6,1,1},{6,6,1,1,1,1,1,1},{6,1,1,1,1,1,1,1,1,1,1,1,1,1,1,},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}. So output should be 7.

Here also , hint given that first use make change of highest denomination. here above example is also in same format.

/   

C ( { 1 , 6 },2 )

this above is the sequence , how problem should divided .

here , we have observe that this problem can be broken into subprolems show we can solve it recursively .

but we also identify here that our subproblems are redundant i.e overlapping subproblems . So for efficient solution we use dynamic programming here .

Algorithm:-

To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain di coin. here i is the highest denomination.
2) Solutions that contain at least one di.
Let count(S[], d1,d2,d3,...di, n) be the function to count the number of solutions, then it can be written as sum of count(S[], d1,d2,d3,..,di-1?, n) and count(S[], d1,d2,d3,...di, n-di).

here , time complexity is O(in) and space complexity is O(n).

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

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