Write programming code that correctly determines the minimum number of coins needed to make change for m cents using denominations {d1, 2, ..., dn}. You must use the following idea:

To find the minimum for k cents, consider the minimum number of coins at each of (k-d1), (k-d2), ... (k-dn) cents. Find the smallest of these, (s say). Suppose it is found at (k-di). Then the minimum number of coins for k cents is s+1, using the coins at (k-di) plus coin di.

Data is supplied in the following order: n d1 d2 ... dn m

Output the minimum number of coins required to make change for m cents followed by the value of each coin. The coins can be printed in any order. [10].

**Solution**

//assumes: n, denom, CoinTable has been initialized

void solve()

{

for(int j = 0; j<=n; j++)

CoinTable[0][j] = 9999; //set the cost of using no denomination to “infinity”

for(int i = 0; i <denom.length; i++)

CoinTable[i][0] = 0; //set the cost of using 0 coins to 0

for(int i=1; i< denom.length; i++)

}

private void printCoins(int n, int m)

{

//assumes: n, denom, CoinTable has been initialized

void solve()

{

for(int j = 0; j<=n; j++)

CoinTable[0][j] = 9999; //set the cost of using no denomination to “infinity”

for(int i = 0; i <denom.length; i++)

CoinTable[i][0] = 0; //set the cost of using 0 coins to 0

for(int i=1; i< denom.length; i++)

for(int j=1; j<=n; j++)

if ( j-denom [i] < 0 ) CoinTable[i][j] = CoinTable[i-1][j]; else C[i][j] = Math.min(CoinTable[i-1][j], CoinTable[i][j-denom [i]]+1 );

}

private void printCoins(int n, int m)

{

if( n < 1 || m < 1 ) return;

if( CoinTable[n][m] == CoinTable[n-1][m] )

{

printCoins(n-1,m);

}

else

{

System.out.println("uses : "+denom [n]);

printCoins(n,m-denom [n]);

}

}

## No comments:

## Post a Comment