贪婪算法
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]);
}
}
}