硬币更换DP解决方案以跟踪硬币 [英] Coin change DP solution to keep track of coins
本文介绍了硬币更换DP解决方案以跟踪硬币的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
尝试为常见的找零问题编程DP解决方案,该解决方案还跟踪使用的硬币。到目前为止,我一直在努力为我提供所需的最低数量的硬币,但无法弄清楚如何使用哪些硬币以及使用了多少次。如果使用了硬币,我尝试用值设置另一个表(布尔值),但这似乎无法正常工作。
有什么想法吗?
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;
*/
}
}
}
}
推荐答案
尝试该解决方案,它仅使用 O(M)内存,并且具有 O(N * M)复杂性:
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;
}
这篇关于硬币更换DP解决方案以跟踪硬币的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文