硬币找零问题（使用动态规划）
硬币找零问题是指使用给定的面额组合达到目标金额的方法数量。
引言
硬币找零问题是指给定一组面额，找到构成目标金额的所有方法数量。假设每种面额的硬币数量无限。例如，使用面额为 1、2、3 的硬币找零 4 元，可能的解有 (1,1,1,1)、(2,2)、(1,1,2)、(1,3)。如你所见，最优解可以是 (2,2) 或 (1,3)。 附带的 Java 程序解决了 “查找所有组合” 和 “查找最优解（使用最少数量的硬币）” 这两个问题。
背景
熟悉 动态规划 将更容易理解该解决方案。请阅读以下文章，以了解该问题的算法视图
CoinChangeAnswer 类
CoinChangeAnswer 的一个实例存储了 FindAll 和 FindOptimal 问题的结果。该类只是一个方便地将结果存储在一个地方的方式。
public class CoinChangeAnswer {
public int OPT[][]; // contains the optimal solution
// during every recurrence step.
public String optimalChange[][]; // string representation of optimal solutions.
/**
* List of all possible solutions for the target
*/
public ArrayList<String> allPossibleChanges = new ArrayList<String>();
/**
* The target amount.
*/
private int target;
/**
* Copy of the denominations that was used to generate this solution
*/
public int[] denoms;
};
所有可能的解
我们首先尝试解决使用面额 1、2、3 凑成目标金额 4 的所有可能方法。如你所见，目标金额 4 可以通过 4 种不同的方式实现，即 (1,1,1,1)、(1,1,2)、(1,3)、(2,2)。让我们尝试达到第一个解 (1,1,1,1)。如果我们选择硬币 '1'，那么剩下的目标金额是 '3'，这是原始问题 '4' 的一个子问题。我们可以看到，使用 '1' 的面额连续解决子问题会导致 '4'。要得到第二个解，我们需要偏离并选择 '2' 在选择 (1,1) 之后。我们如何知道这一点？唯一的方法是穷举地将所有面额放置在所有可能的槽位中，直到达到目标金额。这可以通过构建子问题的递归解决方案来解决。
/**
* Find all possible solutions recursively
* @param tsoln - The current solution string
* @param startIx - The start index in the denomination array.
* @param remainingTarget - The remaining target amount to be satisfied.
* @param answer - The final answer object.
*/
private void findAllCombinationsRecursive(String tsoln,
int startIx,
int remainingTarget,
CoinChangeAnswer answer) {
for(int i=startIx; i<answer.denoms.length ;i++) {
int temp = remainingTarget - answer.denoms[i];
String tempSoln = tsoln + "" + answer.denoms[i]+ ",";
if(temp < 0) {
break;
}
if(temp == 0) {
// reached the answer hence quit from the loop
answer.allPossibleChanges.add(tempSoln);
break;
}
else {
// target not reached, try the solution recursively with the
// current denomination as the start point.
findAllCombinationsRecursive(tempSoln, i, temp, answer);
}
}
}
public CoinChangeAnswer findAllPossibleCombinations(int target, int[] denoms) {
CoinChangeAnswer soln = new CoinChangeAnswer(target,denoms);
String tempSoln = new String();
findAllCombinationsRecursive(tempSoln, 0, target, soln);
return soln;
}
函数 findAllCombinationsRecursive 最初使用以下参数调用：("",0,4,finalAnswer)。finalAnswer 对象是一个数据结构，它将包含要使用的面额和最终解的列表。for 循环从 'startIx' 开始，一直运行到面额的末尾，并通过所选当前面额的值来减少目标金额。如果目标达到零，那么我们有一个解，该解将添加到答案列表中。如果目标 > 0，那么我们需要创建一个子问题，其中 target = target - denoms[i]，并且 denoms[i] 被添加到临时解决方案中。然后，该函数使用 startIx 设置为 'i' 递归调用，这意味着 denoms[i] 将在递归调用中被重新考虑。该算法的复杂度为 O(n^2*T)，其中 n 是面额的数量，T 是目标金额。
最优解
可以使用动态规划找到该程序的最佳解决方案，并且可以通过一种称为记忆化的技术大大减少其运行时间。 本文档 描述了一种算法，我已经将其转换为 Java 函数 findOptimalChange。
/**
* Find the optimal solution for a given target value and the set of denominations
* @param target
* @param denoms
* @return
*/
public CoinChangeAnswer findOptimalChange(int target, int[] denoms) {
CoinChangeAnswer soln = new CoinChangeAnswer(target,denoms);
StringBuilder sb = new StringBuilder();
// initialize the solution structure
for(int i=0; i<soln.OPT[0].length ; i++) {
soln.OPT[0][i] = i;
soln.optimalChange[0][i] = sb.toString();
sb.append(denoms[0]+" ");
}
// Read through the following for more details on the explanation
// of the algorithm.
// http://condor.depaul.edu/~rjohnson/algorithm/coins.pdf
for(int i=1 ; i<denoms.length ; i++) {
for(int j=0; j<target+1 ; j++) {
int value = j;
int targetWithPrevDenomiation = soln.OPT[i-1][j];
int ix = (value) - denoms[i];
if( ix>=0 && (denoms[i] <= value )) {
int x2 = denoms[i] + soln.OPT[i][ix];
if(x2 <= target && (1+soln.OPT[i][ix] < targetWithPrevDenomiation)) {
String temp = soln.optimalChange[i][ix] + denoms[i] + " ";
soln.optimalChange[i][j] = temp;
soln.OPT[i][j] = 1 + soln.OPT[i][ix];
} else {
soln.optimalChange[i][j] = soln.optimalChange[i-1][j]+ " ";
soln.OPT[i][j] = targetWithPrevDenomiation;
}
} else {
soln.optimalChange[i][j] = soln.optimalChange[i-1][j];
soln.OPT[i][j] = targetWithPrevDenomiation;
}
}
}
return soln;
}
历史
- 2009 年 1 月 28 日：初始发布