经典而简单的贪心算法

package endual;

public class Main {

	/**
	 * 题目是：找给顾客的钱的数目最少
	 */
	public static void main(String[] args) {
		
		float backMoney = 70f ; //应找的零钱
		//银行的前是根据现实是设计好的
		float[] backMoneys = {50f, 20f, 10f, 5f, 2f, 1f, 0.5f, 0.2f, 0.1f} ; //目前有的零钱
		int es = answer(backMoney, backMoneys) ; //返回的最少的数目
		System.out.println(es) ;
	}
		/**
		 * 贪心算法
		 */
	private static int  answer(float backMoney, float[] backMoneys) {
	 
		int count = 0 ;
		float lastMoney = backMoney; //初始化的时候应该要找回多
		int n = backMoneys.length ;
		
      for (int i=0; i < n; i++) {
    	  
    	  while(lastMoney >= backMoneys[i]) {
    		  
    		  lastMoney = lastMoney - backMoneys[i] ;
    		  count++ ;
    	  }
    	  if (lastMoney == 0f) {
    		  break ;
    	  }
      }
		return count;
	}

}