高分悬赏：Java语言：有1000 850 700 500 200 100 50 20 10 1这几种面额的纸币，计算某个金额需要最少几张纸币

高分悬赏：Java语言：有1000 850 700 500 200 100 50 20 10 1这几种面额的纸币，计算某个金额需要最少几张纸币
比如2409=1000+700+700+1+1+1+1+1+1+1+1+1 12张

这个主要是利用贪心算法找到最优的解，这里有一篇比较详细的介绍可以参考：https://blog.csdn.net/Pan_ZC/article/details/104583734

public class Test {
    public static void main(String[] args)
    {

        int []denominationType={1000,850,700,500,200,100,50,20,10,1};
        int [] type=new int[denominationType.length];//定义可能出现的类型情况
        for (int i=0;i<denominationType.length;i++){
            int sum=2409;
            int count=0;
            for (int j=0;j<denominationType.length;j++){
                int a;
                int b;
                if(j==0){
                     a= sum%denominationType[i];
                     b=sum/denominationType[i];
                }else if(denominationType[i]==denominationType[j]){
                    continue;
                }else{
                    a= sum%denominationType[j];
                    b=sum/denominationType[j];
                }
                sum=a;
                count+=b;
            }
            type[i]=count;
        }
        int min=type[0];      //定义
        for (int j = 0; j < type.length; j++) {
            if (min > type[j]) {                 // 提取最小可能情况
                min = type[j];
            }
        }
        System.out.println("金额需要最少需要"+min+"张纸币");
    }
}

贪心算法
public static void main(String[] args){
int[] paper = { 1000, 850, 700, 500, 200, 100, 50, 20, 10, 1 };
greedy(2409,paper);
}

public static void greedy(int money,int[] paper) {
    for (int i = 0; i < paper.length; i++) {
        int num = money / paper[i];
        int mod = money % paper[i];
        money = mod;
        if (num > 0) {
            System.out.println( num + "张" + paper[i] + "元");
        }
    }
}