找零钱用贪心法还是动态规划

找零钱问题可以使用贪心算法或动态规划算法进行求解，但两种算法的效果不同。

贪心算法是一种局部最优解策略，它会选择当前最优解并不断更新，但不能保证能够得到全局最优解。对于找零钱问题，贪心算法可以选择面值最大的硬币，然后逐渐减小面值直到凑出所需找零钱，但是如果硬币面值的组合不合适，就可能无法凑出所需的找零钱。

动态规划算法是一种全局最优解策略，它通过将问题分解成子问题来求解整个问题的最优解。对于找零钱问题，动态规划算法可以通过建立一个二维数组来存储各个面值的硬币凑出所需金额的最小硬币数，然后通过递推得到所有金额的最小硬币数。这种方法可以保证得到全局最优解，但需要较多的计算量和空间复杂度。

因此，选择使用贪心算法还是动态规划算法取决于具体问题的特点以及要求解的目标。如果要求得全局最优解，则应该使用动态规划算法；如果只需要得到一个近似最优解，则可以使用贪心算法。

相关问题

贪心法找零钱Java

贪心法是一种常用的解决最优化问题的算法。在找零钱问题中，贪心法是一种可行的算法。具体实现如下：

1. 首先对硬币面值进行从大到小的排序。
2. 从面值最大的硬币开始，将其尽可能多地放入找零钱的集合中，直到无法再放入为止。
3. 接下来考虑面值次大的硬币，重复第2步，直到所有硬币都考虑完毕。

Java代码示例：

public static int[] greedyChange(int[] coins, int money) {
    Arrays.sort(coins);
    int[] result = new int[coins.length];
    for (int i = coins.length - 1; i >= 0; i--) {
        result[i] = money / coins[i];
        money = money % coins[i];
    }
    return result;
}

用c语言计算法解决找零钱问题

好的，下面给出C语言代码实现贪心算法解决找零钱问题：

#include <stdio.h>

int main()
{
    int coins[] = {100, 50, 20, 10, 5, 2, 1}; // 硬币面额
    int n = sizeof(coins) / sizeof(int); // 硬币面额种类数
    int amount, count = 0; // amount: 需要找零的金额, count: 最小硬币数
    printf("请输入需要找零的金额：");
    scanf("%d", &amount);
    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) { // 尽可能使用当前面额的硬币
            amount -= coins[i];
            count++;
        }
    }
    printf("最小硬币数为：%d\n", count);
    return 0;
}

在上述代码中，我们使用了一个整型数组`coins`保存硬币的面额，然后根据硬币面额从大到小的顺序，依次考虑每种面额的硬币，尽可能使用更多的硬币，直到找零的金额为零或者没有更多的当前面额的硬币为止。最后统计使用的硬币数，即为最小硬币数。

当然，这个算法还有一些问题，例如当硬币面额不够细分时，可能会导致找零数目不是最小的。这时候需要使用动态规划等更复杂的算法来解决。