I'm having trouble figuring out my last section of code for a Dynamic Coin Changing Problem. I have included the code below.
I can't figure out the last else
. Should I just use the greedy algorithm at that point or can I calculate the answer from values already in the table? I've worked hard on trying to understand this problem and I think I'm pretty close. The method finds the minimum amount of coins needed to make a certain amout of change by creating a table and using the results that are stored in the table to solve the larger problem without using recursion.
public static int minCoins(int[] denom, int targetAmount){
int denomPosition; // Position in denom[] where the first spot
// is the largest coin and includes every coin
// smaller.
int currentAmount; // The Amount of money that needs to be made
// remainingAmount <= initalAmount
int[][] table = new int[denom.length][targetAmount+1];
for(denomPosition = denom.length-1 ; denomPosition >= 0 ; denomPosition--) {
for(currentAmount = 0 ; currentAmount <= targetAmount ; currentAmount++){
if (denomPosition == denom.length-1){
table[denomPosition][currentAmount] =
currentAmount/denom[denomPosition];
}
else if (currentAmount<denom[denomPosition]){
table[denomPosition][currentAmount] =
table[denomPosition+1][currentAmount];
}
else{
table[denomPosition][currentAmount] =
table[denomPosition+1][currentAmount]-
table[denomPosition][denom[denomPosition]]-1;
}
}
}
return table[0][targetAmount];
}
You don't need to switch to a greedy algorithm for solving the coin changing problem, you can solve it with a dynamic programming algorithm. For instance, like this:
public int minChange(int[] denom, int targetAmount) {
int actualAmount;
int m = denom.length+1;
int n = targetAmount + 1;
int inf = Integer.MAX_VALUE-1;
int[][] table = new int[m][n];
for (int j = 1; j < n; j++)
table[0][j] = inf;
for (int denomPosition = 1; denomPosition < m; denomPosition++) {
for (int currentAmount = 1; currentAmount < n; currentAmount++) {
if (currentAmount - denom[denomPosition-1] >= 0)
actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]];
else
actualAmount = inf;
table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount);
}
}
return table[m-1][n-1];
}
//this works perfectly ...
public int minChange(int[] denom, int targetAmount)
{
int actualAmount;
int m = denom.length+1;
int n = targetAmount + 1;
int inf = Integer.MAX_VALUE-1;
int[][] table = new int[m][n];
for (int j = 1; j < n; j++)
table[0][j] = inf;
for (int i = 1; i < m; i++) //i denotes denominationIndex
{
for (int j = 1; j < n; j++) //j denotes current Amount
{
if (j - denom[i-1] >= 0)//take this denomination value and subtract this value from Current amount
table[i][j] = Math.min(table[i-1][j], 1 + table[i][j - denom[i-1]]);
else
table[i][j] = table[i-1][j];
}
}
//display array
System.out.println("----------------Displaying the 2-D Matrix(denominations and amount)----------------");
for (int i = 0; i < m; i++)
{
System.out.println(" ");
for (int j = 0; j < n; j++)
{
System.out.print(" "+table[i][j]);
}
System.out.println(" ");
}
return table[m-1][n-1];
}
Are you over thinking this? If we were trying to give 68 cents change using U.S. coins…
Would ‘denom’ be { 25, 10, 5, 1 } ?
And wouldn’t the answer be “2 quarters, 1 dime, 1 nickel, and 3 pennies” = ‘2 + 1 + 1 + 3 = 7’? So the function should return the value 7. Right?
This is actually the correct version of this algorithm.
public static int minChange(int[] denom, int targetAmount) {
int actualAmount;
int m = denom.length + 1;
int n = targetAmount + 1;
int inf = Integer.MAX_VALUE - 1;
int[][] table = new int[m][n];
for(int i = 0; i< m; ++i) {
for (int j = 1; j < n; j++) {
table[i][j] = inf;
}
}
for (int denomPosition = 1; denomPosition < m; denomPosition++) {
for (int currentAmount = 1; currentAmount < n; currentAmount++) {
if (denom[denomPosition-1] <= currentAmount) {
// take
actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]];
}
else {
actualAmount = inf;
} // do not take
table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount);
}
}
return table[m-1][n-1];
}