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;
*/
}
}
}
}
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;
}