初识贪心—-硬币支付问题

Java基础

浏览数:81

2019-10-8

AD:资源代下载服务

题目:

  有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚。现在要用这些硬币来支付A元,最少需要多少枚硬币?假定本题至少存在一种支付方案。0≤ci≤109,0≤A≤109

  输入:第一行有六个数字,分别代表从小到大6种面值的硬币的个数,第二行为A,代表需支付的A元。

  样例:

  输入:

3 2 1 3 0 2
620

  输出:

6

分析:如果我们每次选面值尽可能大的,就能保证硬币数越小,(可用反证法证明正确性)。因为不用大面值,将使用更多的小面值硬币,一定得不到最优解。

代码:

import java.util.Scanner;

public class 硬币支付 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 6; i++) {
            cnts[i] = sc.nextInt();
        }
        int A = sc.nextInt();
        int res = f(A, 5);
        System.out.println(res);
    }

    static int[] cnts = new int[6];
    static int[] coins = { 1, 5, 10, 50, 100, 500 };

    static int f(int A, int cur) {
        if (A <= 0)
            return 0;
        if (cur == 0)
            return A;

        int coinValue = coins[cur];
        int x = A / coinValue;// 金额有多少个coinValue
        int cnt = cnts[cur];// 当前面值的硬币有cnt个
        int t = Math.min(x, cnt);
        return t + f(A - t * coinValue, cur - 1);// 用t个当前面值,剩下的继续处理
    }

}

结果:

  

 

作者:|旧市拾荒|