贪心算法——有1元，5元，10元，50元，100元，500元的硬币各C1，C5，C10，C50，C100，C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？

有1元，5元，10元，50元，100元，500元的硬币各C1，C5，C10，C50，C100，C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？

先从面值最大的硬币往小遍历，用大面值的硬币越多，总数就越少

贪心算法思路：

for (int i = b.length - 1; i >= 0; i–)

1. 尽可能多地使用面值为500元的硬币
   2. 再尽可能多地使用面值为100元的硬币
      3. 再尽可能多地使用面值为50元的硬币
         4. 再尽可能多地使用面值为10元的硬币
            5. 再尽可能多地使用面值为5元的硬币
               6. 再尽可能多地使用面值为1元的硬币

}

public class Main {

	public static void main(String[] args) {
		int[] a = { 1, 5, 10, 50, 100, 500 };//面值
		int[] b = new int[6];//输入的个数
		int pay = 0; //客户支付金额
		int count = 0;
		Scanner scanner = new Scanner(System.in);
		for (int i = 0; i < b.length; i++) {
			b[i] = scanner.nextInt();
		}
		pay = scanner.nextInt();
		for (int i = b.length - 1; i >= 0; i--) {
			int n = Math.min(pay/ a[i], b[i]); //n = (当前硬币数  ， 实际硬币数 ) 取最小值
			pay = pay - a[i] * n;	//当前剩余金额
			count += n;
		}
		if (pay == 0) {
			System.out.println(count);
		}else {
			System.out.println("凑不到");
		}

	}
}

最后

以上就是简单荷花为你收集整理的贪心算法——有1元，5元，10元，50元，100元，500元的硬币各C1，C5，C10，C50，C100，C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？的全部内容，希望文章能够帮你解决贪心算法——有1元，5元，10元，50元，100元，500元的硬币各C1，C5，C10，C50，C100，C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。