贪心算法

概念

总的来说是每次都使用目前看起来最优的选择。每一次都这样操作，最终的结果也极大可能是最优的，或者是它能产生与最优解相似的解法。
  

1. 把求解的问题分成若干个子问题。  
2. 对每一子问题求解，得到子问题的局部最优解。  
3. 把子问题的局部最优解合成原来问题的一个解。

小明手中有 1，5，10，50，100 五种面额的纸币，每种纸币对应张数分别为 5，2，2，3，5 张。若小明需要支付 456 元，则需要多少张纸币？
很显然，每次的最优解是使用最大面额的纸币。所以每次都尽可能的使用更大面额的纸币。

代码

	int[] i1 = {100,50,10,5,1};
		int[] i2 = {5,2,2,3,5};
		int n = 456;
		int ans = 0;
	
	for (int j = 0; j < i1.length; j++) {
		System.out.println("*"+i2[j]);
		int num = n/i1[j];
		for (int i = 0; i <= num; i++) {
			if (i2[j] == 0) break;
			if (n - i1[j] >= 0) {
			n -= i1[j]	
			System.out.println(n);
			i2[j]--;
			ans++;
			}
		}
	}

		System.out.println(ans);