贪婪算法

2019-01-08  本文已影响0人  jiamjg

贪婪算法的基本思路:
从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时,就停止算法,给出近似解。
由贪婪算法的特点和思路可看出,该算法存在以下问题:

换零钱

该程序实现超市收银的找零方案,输入需要找补给顾客的金额,由程序计算出该金额可有哪些面值人民币组成。人民币假设有100,50,20,10,5,2,1,0.5,0.2,0.1

import java.util.Scanner;

public class chargeMoney {
    static double money[]= {10000,5000,2000,1000,500,200,100,50,20,10};   //乘100,不让容易错
    static int num[]=new int[10];
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        double mon=input.nextDouble();
        double tmon=mon*100;   //记得乘100,临时变量
        int i;
        for(i=0;i<10;i++) {
            if(tmon>money[i]) {
                break;
            }
        }
        while(tmon>0&&i<10) {
            if(tmon>=money[i]) {
                tmon-=money[i];
                num[i]++;
            }else if(tmon<10&&tmon>=5) {
                num[9]++;
                break;
            }else {
                i++;
            }
        }
        for(int j=0;j<10;j++) {
            if(num[j]==0) {
                continue;
            }
            System.out.println(money[j]/100+":"+num[j]);
        }
    }
}
上一篇下一篇

猜你喜欢

热点阅读