Please work on part b), which is write a dynamic algorithm in Java to compute C(
ID: 3711517 • Letter: P
Question
Please work on part b), which is write a dynamic algorithm in Java to compute C(n). Thank you!
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 [d,... , dl 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 (,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
Solution:
Dynamic programming Algorithm:
int minCoins(int deno[], int m, int V)
{
// table[i] will be storing the minimum number of coins
// required for i value. So table[V] will have result
int table[V+1];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i=1; i<=V; i++)
table[i] = INT_MAX;
// Compute minimum coins required for all
// values from 1 to V
for (int i=1; i<=V; i++)
{
// Go through all coins smaller than i
for (int j=0; j<m; j++)
if (deno[j] <= i)
{
int sub_res = table[i-deno[j]];
if (sub_res != INT_MAX && sub_res + 1 < table[i])
table[i] = sub_res + 1;
}
}
return table[V];
}
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)