硬币

可以使用任意数量的 a元硬币、b 元硬币和 c 元硬币。请找出恰好凑出 n 元所需的最小硬币总数。若无法凑出，则输出 -1。

时间限制：1000ms，内存限制：256MB

输入格式

第一行，整数 n；

第二行，三个整数表示 a、b、c。

输出格式

输出最小硬币总数（若无法凑出则输出 -1）。

输入样例#1

100
20 40 50

输出样例#1

2

输入样例#2

99
1 5 10

输出样例#2

14

数据范围：

1≤N≤10⁹；1≤A≤B≤C≤10⁹。保证最终最小硬币总数不超过10⁴。

首先，我们可以使用贪心算法来解决这个问题。贪心算法的基本思想是从最大的硬币开始使用，逐步减小凑出的金额。具体步骤如下：

1. 从最大的硬币面值开始尝试使用，尽可能多地使用这种硬币，直到无法再使用或者凑出金额等于目标值。
2. 然后使用次大的硬币面值继续尝试凑出剩余金额，以此类推。
3. 如果最终凑出的金额等于目标值n，记录使用的硬币数量并返回；否则返回-1。

以下是C语言的代码实现：

#include <stdio.h>

int main() {
    int n, a, b, c;
    scanf("%d %d %d %d", &n, &a, &b, &c); // 读入目标金额和硬币面值
    int count = 0; // 记录硬币总数
    int i;
    for (i = c; i >= a && n > 0; i--) { // 从最大的硬币面值开始尝试使用
        int temp = n / i; // 计算当前硬币面值能使用的最大数量
        count += temp; // 累加硬币数量
        n -= temp * i; // 更新剩余金额
    }
    if (n == 0) { // 如果最终凑出金额等于目标值n，返回硬币数量
        printf("%d\n", count);
    } else { // 无法凑出目标值，返回-1
        printf("-1\n");
    }
    return 0;
}

贪心算法是一种常用的优化方法，其基本思想是在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优。在这个问题中，我们优先使用面值较大的硬币，以尽量减少所需的硬币数量。由于数据范围较大，我们需要使用适当的优化方法来处理数据，避免超时或内存溢出。