动态规划算法求解硬币找零问题

动态规划算法求解硬币找零问题

?

动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后在求解较大子问题的时候需要用到这些子问题的解，就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式，例如保存在数组中。

public class CoinsChange { /** * 硬币找零：动态规划算法 * * @param values * :保存每一种硬币的币值的数组 * @param valueKinds * :币值不同的硬币种类数量，即coinValue[]数组的大小 * @param money * :需要找零的面值 * @param coinsUsed * :保存面值为i的纸币找零所需的最小硬币数 */ public static void makeChange(int[] values, int valueKinds, int money, int[] coinsUsed) { coinsUsed[0] = 0; // 对每一分钱都找零，即保存子问题的解以备用，即填表 for (int cents = 1; cents <= money; cents++) { // 当用最小币值的硬币找零时，所需硬币数量最多 int minCoins = cents; // 遍历每一种面值的硬币，看是否可作为找零的其中之一 for (int kind = 0; kind < valueKinds; kind++) { // 若当前面值的硬币小于当前的cents则分解问题并查表 if (values[kind] <= cents) { int temp = coinsUsed[cents - values[kind]] + 1; if (temp < minCoins) { minCoins = temp; } } } // 保存最小硬币数 coinsUsed[cents] = minCoins; System.out.println("面值为 " + (cents) + " 的最小硬币数 : " + coinsUsed[cents]); } } public static void main(String[] args) { // 硬币面值预先已经按降序排列 int[] coinValue = new int[] { 25, 21, 10, 5, 1 }; // 需要找零的面值 int money = 63; // 保存每一个面值找零所需的最小硬币数，0号单元舍弃不用，所以要多加1 int[] coinsUsed = new int[money + 1]; makeChange(coinValue, coinValue.length, money, coinsUsed); } }

?

面值为 1 的最小硬币数 : 1
面值为 2 的最小硬币数 : 2
面值为 3 的最小硬币数 : 3
面值为 4 的最小硬币数 : 4
面值为 5 的最小硬币数 : 1
面值为 6 的最小硬币数 : 2
...
...
面值为 60 的最小硬币数 : 3
面值为 61 的最小硬币数 : 4
面值为 62 的最小硬币数 : 4
面值为 63 的最小硬币数 : 3

?上面的代码并没有给出具体应该是哪几个面值的硬币，这个可以再使用一些数组保存而打印出来。