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];
}
Making Change problem is to find change for a given amount using a minimum number of coins from a set of denominations. Explanation : If we are given a set of denominations D = {d0, d1, d2, …, dn} and if we want to change for some amount N, many combinations are possible.
In Dynamic programming problems, Time Complexity is the number of unique states/subproblems * time taken per state. In this problem, for a given n, there are n unique states/subproblems. For convenience, each state is said to be solved in a constant time. Hence the time complexity is O(n * 1).
Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems.
The change-making problem addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a special case of the integer knapsack problem, and has applications wider than just currency.
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];
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With