贪心算法在找零问题中的应用

创作时间:

作者:

@小白创作中心

贪心算法在找零问题中的应用

引用

CSDN

https://blog.csdn.net/lzyzuixin/article/details/138075846

找零问题是一个经典的优化问题，其目标是用最少的硬币找零给定的金额。贪心算法是解决这类问题的一种常用方法，其核心思想是在每一步选择中都采取最好或最优（即最有利）的选择，从而希望能够导致全局的最好或最优的解。本文将围绕找零问题展开，通过贪心算法设计解决方案，并证明在特定条件下贪心算法的有效性。同时，也将探讨贪心算法失效的情况，并设计一种通用的找零算法。

a. 贪心算法求解找零问题

算法设计

假设我们有25美分、10美分、5美分和1美分四种面额的硬币。贪心算法的策略是尽可能多地使用面额较大的硬币，以减少硬币的总数。

初始化找零金额n。
如果n大于等于25美分，则从n中减去25美分，并增加25美分硬币的数量。
如果n大于等于10美分且小于25美分，则从n中减去10美分，并增加10美分硬币的数量。
如果n大于等于5美分且小于10美分，则从n中减去5美分，并增加5美分硬币的数量。
如果n小于5美分，则直接使用1美分硬币找零。

算法证明

为了证明贪心算法的有效性，我们需要证明在每一步选择中，使用面额最大的硬币总是能得到最优解。

设最优解中使用了k个面额为c的硬币，而贪心算法使用了m个面额为c的硬币。如果k>m，则可以通过将k-m个面额为c的硬币替换为更小面额的硬币来得到一个更好的解，这与最优解的定义矛盾。因此，k<=m，即贪心算法得到的解不会比最优解差。

b. 硬币面额为c的幂时的贪心算法证明

当硬币面额为c的幂时（例如1, c, c^2, c^3...），贪心算法总是能得到最优解。

算法设计

初始化找零金额n。
从最大面额的硬币开始，尽可能多地使用该面额的硬币。
重复步骤2，直到找零金额为0。

算法证明

设最优解中使用了k个面额为c^i的硬币，而贪心算法使用了m个面额为c^i的硬币。如果k>m，则可以通过将k-m个面额为c^i的硬币替换为更小面额的硬币来得到一个更好的解，这与最优解的定义矛盾。因此，k<=m，即贪心算法得到的解不会比最优解差。

c. 设计使贪心算法失效的硬币面额组合

虽然贪心算法在大多数情况下都能得到最优解，但在某些特定的硬币面额组合下，贪心算法可能会失效。例如，假设硬币面额为1, 3, 4，需要找零6美分。按照贪心算法，会先选择4美分的硬币，然后选择2个1美分的硬币，共使用3个硬币。但实际上，使用2个3美分的硬币就能完成找零，只使用2个硬币。

d. 通用找零算法设计

为了克服贪心算法的局限性，可以使用动态规划来设计一个通用的找零算法。

算法设计

定义dp[i]为找零i美分所需的最少硬币数量。
初始化dp[0]=0，dp[i]=无穷大（i>0）。
对于每种面额的硬币c，更新dp数组：dp[i] = min(dp[i], dp[i-c]+1)（i>=c）。

算法实现（伪代码）

function coinChange(coins, amount):
    dp = [0] + [float('inf')] * amount
    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i-coin]+1)
    return dp[amount] if dp[amount] != float('inf') else -1

算法实现（C代码）

#include <stdio.h>
#include <stdlib.h>

int coinChange(int* coins, int coinsSize, int amount) {
    int* dp = (int*)malloc((amount+1) * sizeof(int));
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < coinsSize; j++) {
            if (i >= coins[j] && dp[i-coins[j]] != INT_MAX) {
                dp[i] = fmin(dp[i], dp[i-coins[j]]+1);
            }
        }
    }
    int result = (dp[amount] == INT_MAX) ? -1 : dp[amount];
    free(dp);
    return result;
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 11;
    int result = coinChange(coins, 3, amount);
    printf("Minimum coins needed: %d\n", result);
    return 0;
}