贪心算法之找零钱

174 阅读 0 评论 115 点赞

我是靠谱客的博主大胆宝贝，这篇文章主要介绍贪心算法之找零钱，现在分享给大家，希望可以做个参考。

问题描述：

当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）

代码

import java.util.Scanner;

/**
 * 贪心算法
 */

public class Main {

	public static void main(String[] args) {
		int[] money = new int[]{25,10,5,1};	//先对硬币按面值从大到小排序
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int num[] = new int[money.length];
		
			for (int i = 0; i < money.length; i++) {	
				num[i] = n/money[i];
				n = n%money[i];
			}
		for (int i = 0; i < num.length; i++) {
			System.out.println(money[i]+"分面值的硬币"+num[i]+"枚");
		}
	}
}

贪心算法得出来的不是最优解，但是对于部分问题还是可以解决的。