找零钱问题的贪心算法.pdf

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。在找零钱问题中，贪心策略是每次都选取最大面值的硬币来尽可能多地减少硬币的数量。这种策略基于一个假设：每次选择局部最优解，最终会得到全局最优解。 找零钱问题的具体描述是这样的：给定一组硬币面值，如2角5分、1角、5分和1分，目标是找出找给顾客n分钱时所需的最少硬币数量。这是一个典型的组合优化问题，可以通过贪心算法来解决。 问题分析： 1. 贪心选择性质：每次选取当前可选的最大面值硬币。这是因为如果先选取小面值的硬币，即使后面可以用大面值的硬币替换，也会增加总的硬币数。 2. 完全背包问题：这个问题可以类比于完全背包问题，因为在找零钱时，每种面值的硬币数量通常是无限的。 算法设计与实现： 1. 初始化：创建一个长度为硬币面值数组m长度的num数组，用于存储每种面值硬币的数量。 2. 主循环：遍历硬币面值数组m，对于每个面值，计算能用该面值硬币找零的最大数量，并更新剩余需要找零的金额n。 3. 结束条件：当n等于0时，找零完成，返回num数组，否则继续下一个面值的处理。 Java代码实现如下： ```java public class ChangeMaking { public static int[] zhaoqian(int m[], int n) { int k = m.length; int[] num = new int[k]; for (int i = 0; i < k; i++) { num[i] = n / m[i]; n = n % m[i]; } return num; } public static void main(String[] args) { int m[] = {25, 10, 5, 1}; int n = 99; int[] num = new int[m.length]; num = zhaoqian(m, n); System.out.println(n + "的找钱方案："); for (int i = 0; i < m.length; i++) System.out.println(num[i] + "枚" + m[i] + "面值"); } } ``` 这段代码首先定义了一个静态方法`zhaoqian`，它接收硬币面值数组m和需要找零的金额n，然后计算出每种面值硬币的数量，并将结果存放在num数组中。在`main`方法中，我们初始化了硬币面值和找零金额，调用`zhaoqian`方法并打印出找零方案。 需要注意的是，贪心算法并不总是能得到全局最优解。例如，在某些情况下，如果限制了每种面值硬币的最大数量，或者面值不是连续的，那么贪心策略可能无法找到最优解。在这种情况下，可能需要使用动态规划等其他算法来求解。然而，对于本问题的设定，贪心算法是有效的，因为它符合问题的贪心选择性质。