Coin change DP solution to keep track of coins
11,094
Solution 1
Try this solution, it used only O(M) memory and has O(N*M) complexity:
public static int[] minChange(int[] denom, int changeAmount)
{
int n = denom.length;
int[] count = new int[changeAmount + 1];
int[] from = new int[changeAmount + 1];
count[0] = 1;
for (int i = 0 ; i < changeAmount; i++)
if (count[i] > 0)
for (int j = 0; j < n; j++)
{
int p = i + denom[j];
if (p <= changeAmount)
{
if (count[p] == 0 || count[p] > count[i] + 1)
{
count[p] = count[i] + 1;
from[p] = j;
}
}
}
// No solutions:
if (count[changeAmount] == 0)
return null;
// Build answer.
int[] result = new int[count[changeAmount] - 1];
int k = changeAmount;
while (k > 0)
{
result[count[k] - 2] = denom[from[k]];
k = k - denom[from[k]];
}
return result;
}
Solution 2
public static int minimumNumberOfWays(int []deno, int amount){
int dp[] = new int[amount+1];
dp[0]=0;
int []prevCoin = new int[amount+1];
for(int j=1;j<=amount;j++){
dp[j]=Integer.MAX_VALUE;
for(int i=0;i<deno.length;i++){
if(deno[i]<=j && (1+dp[j-deno[i]] < dp[j]) ){
dp[j]=1+dp[j-deno[i]];
prevCoin[j]=deno[i];
}
}
}
int result = dp[amount];
List<Integer> coinsAdded = new ArrayList<Integer>();
for(int i=amount;i>=1;){
coinsAdded.add(prevCoin[i]);
int j=i;
i=amount-prevCoin[i];
amount = amount - prevCoin[j];
}
Integer [] coins = coinsAdded.toArray(new Integer[coinsAdded.size()]);
System.out.println( Arrays.toString(coins));
Author by
Admin
Updated on June 04, 2022Comments
-
Admin almost 2 years
Trying to program a DP solution for the general coin-change problem that also keeps track of which coins are used. So far I have it working to give me the minimum amount of coins needed but can't figure out how to get which coins were used and how many times. I tried setting up another table (boolean) with values if the coin is used but that doesn't seem to work correctly. Any ideas?
public static int minChange(int[] denom, int changeAmount) { int m = denom.length; int n = changeAmount + 1; int[][] table = new int[m][n]; boolean[][] used = new boolean[m][n]; for (int j = 0; j < n; j++) table[m - 1][j] = j; for (int i = 0; i < m; i++) table[i][0] = 0; for (int i = m-2; i >= 0; i--) //i denotes denominationIndex { for (int j = 1; j < n; j++) //j denotes current Amount { if (denom[i] > j) { table[i][j] = table[i+1][j]; //used[i][j] = false; } else { table[i][j] = Math.min(1 + table[i][j-denom[i]], table[i+1][j]); /*Trying table for used coins if (1 + table[i][j-denom[i]] < table[i+1][j]) used[i][j] = true; else used[i][j] = false; */ } } } }
-
Dinuka Thilanga almost 9 yearswhat is M in complexity?
-
Vetterjack over 5 yearsThis is a greedy approach, not DP! Greedy does not always find the optimal solution.
-
Jeroen Steenbeeke about 3 yearsWhile this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.