贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

1.算法概述

贪心算法可以简单描述为：大事化小，小事化了。对于一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题。并且对于每个子问题的解进行选择，找出最优值，进行处理，再找出最优值，再处理。也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到结果是最好或最优的算法。

2.算法流程

1）建立数学模型来描述问题。 2）把求解的问题分成若干个子问题。 3）对每一子问题求解，得到子问题的局部最优解。 4）把子问题的局部最优解合成原来问题的一个解。

3.实例

小明手中有 1，5，10，50，100 五种面额的纸币，每种纸币对应张数分别为 5，2，2，3，5 张。若小明需要支付 456 元，则需要多少张纸币？

制定的贪心策略为：在允许的条件下选择面额最大的纸币。则整个求解过程如下：

选取面值为 100 的纸币，则 X1 = 100, V = 456 – 100 = 356；

继续选取面值为 100 的纸币，则 X2 = 100, V = 356 – 100 = 256；

继续选取面值为 100 的纸币，则 X3 = 100, V = 256 – 100 = 156；

继续选取面值为 100 的纸币，则 X4 = 100, V = 156 – 100 = 56；

选取面值为 50 的纸币，则 X5 = 50, V = 56 – 50 = 6；

选取面值为 5 的纸币，则 X6 = 5, V = 6 – 5 = 1；

选取面值为 1 的纸币，则 X7 = 1, V = 1 – 1 = 0；求解结束

将所有解元素合并为原问题的解。

小明需要支付的纸币张数为 7 张，其中面值 100 元的 4 张，50 元 1 张，5 元 1 张，1 元 1 张。

4.代码实现

int[] counts = {5,2,2,3,5}; //每种纸币的数量
int[] values = {1,5,10,50,100}; //币种数组
int initMoney = 465; //要凑足的金额数量
int money = initMoney;
int iCount=0; //需要的钞票数量
for(int i=values.length-1;i>=0;i--){
    int temp = Math.min(money/values[i],counts[i]);
    money -= temp*values[i];
    iCount+=temp;
}
if(money>0){
    iCount=-1;
    System.out.println("无法凑足" + initMoney + "元");
    return;
}

System.out.println("需要" + iCount + "张钞票凑足" + initMoney + "元");

运行结果：
需要7张钞票凑足465元