经典算法贪心(刷题归纳)

<贪心算法greedy algorithnm>

本质是让机器模拟人类，每次都按照某一个标准取最优解，一般常用最优子结构问题，但不是所有的时候贪心都获得最优解。

跟DP最大的区别在于，贪心不可以回溯

<栗子>

艾伦是一个非常富有的人，他在银行存有 n 元钱，现在由于某些私人原因，他要将钱全部取出用于急用。

已知银行的钞票共分 1,5,10,20,100这 5种面值。

出于携带方便的考虑，艾伦希望组成这 n元钱的钞票张数尽可能少。

请问在给定 n 的情况下，组成 n元钱的钞票张数最少是多少。

输入格式

共一行，只包含一个整数 n。

输出格式

共一行，只包含一个整数，表示最少的钞票张数。

解题思路：首先考虑100够不够取.........，进行依次类推

代码实现：

import java.util.Scanner;
public class Main{
    public static void main(String[]args)
    {
        Scanner input=new Scanner(System.in);
        int []ant={0,100,20,10,5,1};
        int n= input.nextInt();
        int count=0;
        for(int i=1;i<=5;i++)
        {
            int t=n/ant[i];
            n-=ant[i]*t;
            count+=t;

        }
        System.out.println(count);
    }
}