贪心算法(硬币找零问题)

问题描述

小Q手上有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出1到 m 之间的任意值。输入的第一行为两个整数：m 和 n，他们的意义如题目描述。 接下来的 n 行，每行一个整数，第i+1 行的整数表示第 i 种硬币的面值。输出的最少需要携带的硬币数量，如果无解则输出-1。
50%的数据：1<=n<=10， 1<=m<=10^3；
100%的数据：1<=n<=100，1<=m<=10^9；

输入：

20 4 
1 
2 
5 
10

输出：

5

思路：

数据量很大，dp不好做，也不好压缩，应该采用贪心的思路。首先如果没有面值为1的硬币必定无法满足要求可以直接输出-1，接下来考虑贪心策略，设想如果能够组合出1到5之间的任何数值，只要一个6的硬币就能组合出1到11的任意值，既如果当前能够组合出1到n的硬币，再加入一个n+1面值的银币就能组合出1到n+n+1的所有面值。所以基本思路就是用一个变量cur存储当前能表示的面值，将硬币排序，从大往小找到第一个小于等于cur+1的硬币，硬币数加一同时更新cur，当cur大于m时输出。

代码：

import java.util.*;
public class Main {
    public static void main(String arg[]){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int m = in.nextInt();
            int n = in.nextInt();
            int coin[] = new int[n];
            for (int i=0; i<n; i++){
                coin[i] = in.nextInt();
            }
            Arrays.sort(coin);
            if (coin[0] != 1){
                System.out.println(-1);
                continue;
            }
            int cur = 0, count = 0;
            while (cur < m){
                for (int i=coin.length-1; i>=0; i--){
                    if (coin[i] <= cur + 1){
                        count++;
                        cur += coin[i];
                        break;
                    }
                }
            }
            System.out.println(count);
        }
    }
}