贪婪算法

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

   -不能保证最后的解释最优的;

   -不能用来求最大或者最小解的问题;

   -只能求满足某些约束条件的可行解得范围.

实例:换零钱

 

Java代码描述

public class Test {

	static int MAXN = 9;
	static int[] parvalue = {10000,5000,1000,500,200,100,50,20,10};
	static int[] num = new int[9];
	
	public static void main(String[] args) {
		int i;
		float m;
		System.out.println("请输入要处理的金额");
		Scanner sc = new Scanner(System.in);
		m = sc.nextFloat();
		exchange((int)(100*m));
		System.out.println("零钱组成为");
		for(i=0;i<MAXN;i++){
			if(num[i]>0){
				System.out.println((float)(parvalue[i]/100.0)+"元 "+num[i]+"张");
			}
		}
	}
	
	public static void exchange(int n){
		int i;
		for(i = 0;i<MAXN;i++){
			if(n>parvalue[i]){	//找到最大面额
				break;
			}
		}
		while(n>0&&i<MAXN){		//循环寻找逐渐小的面额
			if(n>=parvalue[i]){
				n-=parvalue[i];	//拿到当前面额最大的一张
				num[i]++;		//当前面额计数器加一
			}else if(n<10&&n>=5){
				num[MAXN-1]++;
				break;
			}else{
				i++;
			}
		}
	}	
}

 运行结果: