基于贪心算法钱币找零

基于贪心算法的钱币找零问题是指在给定一定面额的硬币和一个需要找零的金额时，如何使用最少数量的硬币找零。贪心算法的思想是每次选择面额最大的硬币，直到找零金额为0或者无法再找到更大面额的硬币为止。

以下是基于贪心算法的钱币找零的Python代码实现：

def coinChange(coins, amount):
    coins.sort(reverse=True) # 将硬币面额从大到小排序
    res = 0
    for coin in coins:
        if amount >= coin:
            res += amount // coin # 计算当前面额硬币的数量
            amount %= coin # 计算剩余需要找零的金额
    if amount != 0:
        return -1 # 如果无法找零，则返回-1
    return res

coins = [1, 5, 10, 50, 100]
amount = 123
print(coinChange(coins, amount)) # 输出：5

上述代码中，我们首先将硬币面额从大到小排序，然后依次选择面额最大的硬币，计算当前面额硬币的数量，并计算剩余需要找零的金额。如果无法找零，则返回-1。

相关问题

钱币找零问题给出思路以及算法实现

钱币找零问题是指给定一个总金额和一些面额不同的硬币，求出最少需要多少个硬币来凑成这个总金额。这个问题可以用贪心算法来解决。

贪心算法的思路是从面额最大的硬币开始，尽可能多地使用该硬币，直到不能再使用该硬币为止，然后再使用次大面额的硬币，以此类推，直到凑够总金额。

具体的算法实现如下：

1. 将硬币面额按照从大到小的顺序排序。
2. 从面额最大的硬币开始，尽可能多地使用该硬币，直到不能再使用该硬币为止。
3. 使用次大面额的硬币，重复步骤2，直到凑够总金额。

下面是一个Python代码实现：

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count if amount == 0 else -1

其中，coins是硬币面额的列表，amount是总金额。如果可以凑够总金额，则返回最少需要的硬币数量，否则返回-1表示无法凑够。

贪心算法几个经典例子

引用中提到了两个贪心算法的经典例子：钱币找零问题和活动选择问题。在钱币找零问题中，贪心算法会优先选择面值大的钱币，以此类推，直到凑齐总金额。而在活动选择问题中，贪心算法会选择活动的结束时间最早的活动，然后继续选择与该活动不冲突的结束时间最早的活动，以此类推，直到所有活动都被选择或者没有可选的活动了。下面是两个例子的具体实现：

例题1：钱币找零问题

/** 
 * 贪心算法：钱币找零问题
 * @param sum 总金额
 * @param values 钱币面额
 * @param counts 钱币数量
 * @return 每种面额的数量
 */
public int[] getNumber1(int sum, int[] values, int[] counts) {
    int[] result = new int[values.length];
    int add = 0; // 当前凑的金额
    for (int i = values.length - 1; i >= 0; i--) {
        int num = (sum - add) / values[i];
        if (num > counts[i]) {
            num = counts[i];
        }
        add += num * values[i];
        result[i] = num;
    }
    return result;
}

例题2：活动选择问题

/**
 * 贪心算法：活动选择问题
 * @param start 活动开始时间数组
 * @param end 活动结束时间数组
 * @return 所选活动的索引
 */
public List<Integer> activitySelection(int[] start, int[] end) {
    List<Integer> selectedActivities = new ArrayList<>();
    int n = start.length;
    selectedActivities.add(0); // 选择第一个活动
    int lastSelected = 0;
    for (int i = 1; i < n; i++) {
        if (start[i] >= end[lastSelected]) {
            selectedActivities.add(i);
            lastSelected = i;
        }
    }
    return selectedActivities;
}