Java实现贪心算法（找零钱问题）

1 package com.java; 2  3 import java.util.Random; 4 /** 5  * 贪心算法 6  * 贪心算法，又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择。 7  * 也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。 8  * 9  * 贪心算法的基本思路如下：10  * 1.建立数学模型来描述问题。11  * 2.把求解的问题分成若干个子问题。12  * 3.对每一子问题求解，得到子问题的局部最优解。13  * 4.把子问题的局部最优解合成原来解问题的一个解。14  *15  * 其实现框架如下：16  * 从问题的某一初始解出发；17  * while （能朝给定总目标前进一步）18  * {19  * 利用可行的决策，求出可行解的一个解元素；20  * }21  * 由所有解元素组合成问题的一个可行解。22  */23 24 /**25  * 钱币找零问题描述：26  * 假设1元、2元、5元、10元、20元、50元、100元的纸币，分别有c0, c1, c2, c3, c4, c5, c6张。27  * 现在要用这些钱来支付K元，至少要用多少张纸币？28  * 用贪心算法的思想：29  * 每一步尽可能用面值大的纸币，在程序中需要事先将Value按照从小到大的顺序排好。30  */31 public class Greed {32 33     //人民币面值集合34     static int[] values = {1, 2, 5, 10, 20, 50, 100};35     //各种面值对应数量集合36     static int[] counts = {20, 10, 20, 11, 6, 3, 5};37 38     public static void main(String[] args) {39         Random ra = new Random();40         int chgn = ra.nextInt(500) + 1;41         int[] num = change(chgn, values, counts);42         System.out.println("需要找零面额\t： " + chgn);43         System.out.println("-------------------------\r\n应找：");44         print(num, values);45     }46 47     /** Function:change 找零钱48      * @param money:人民币数额49      * @param values:面值集合 数组50      * @param counts:现有各面值对应数量集合 数组51      * @return: 各面值需要数量集合 数组52      */53     public static int[] change(int money, int[] values, int[] counts) {54         //用来记录需要的各种面值张数55         int[] result = new int[values.length];56 57         for (int i = values.length - 1; i >= 0; i--) {58             //需要最大面值人民币张数59             int c = Math.min(money / values[i], counts[i]);60             //剩下钱数61             money = money - c * values[i];62             //将需要最大面值人民币张数存入数组63             result[i] = c;64         }65         return result;66     }67 68     private static void print(int[] num, int[] values) {69         for (int i = 0; i < values.length; i++) {70             if (num[i] != 0) {71                 System.out.println("面额为 " + values[i] + "\t元： " + num[i] + "\t张");72             }73         }74     }75 }