In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An

Question

In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An algorithm for making change using the smallest possible number of coins repeatedly returns the biggest coin smaller than the amount to be changed until it is zero. For example, 17 cents will result in the series 10 cents, 5 cents, 1 cent, and 1 cent 1) cd), describe an algorithm that uses dynamic Given a set of arbitrary denominations c=(c programming to compute the minimum number of coins required for making change. You may assume that c contains 1 cent 2) Implement the algorithm described in 1) using Java language by completing the given method declaration. You must use dynamic programming implementation. public static int numOfCoins(int[] coinsList, int value) /* * Write your code here to find out minimum number of coins required to provide the change for a given value This method will have a coinsList array, which can be any set of coin values that should be used to test the code. You cannot hard code this array because the array value will be giving at runtime, and an int value which specifies the value for which we need to calculate the minimum number of coins to be changed. This method should return the number of coins Example using non-recursive implementation int coins1st [5] {50, 25, 10, numofCoins (int value) 5, 1); if (value

Explanation / Answer

class CoinsCount

{

static int minOfCoins(int coins[], int n)

{

int m = coins.length;

if (n == 0) return 0;

int res = Integer.MAX_VALUE;

for (int i=0; i<m; i++)

{

if (coins[i] <= n)

{

int sub_res = minOfCoins(coins,n-coins[i]);

if (sub_res != Integer.MAX_VALUE && sub_res + 1 < res)

res = sub_res + 1;

}

}

return res;

}

public static void main(String args[])

{

int coins[] = {50,25,10,5,1};

int n = 17;

System.out.println("Minimum coins required is "+ minOfCoins(coins,n) );

}

}

OUTPUT:

Minimum coins required is : 4

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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