用C语言编写程序实现银行换零钱问题

在C语言中，银行换零钱问题通常是一个经典的动态规划或递归问题，也称为“硬币找零”问题。这个问题的基本思想是要计算给定面额数组和总金额，找到一种组合方式来支付最少的硬币数量。

下面是一个简单的示例代码：

#include <stdio.h>

// 定义最大面额
#define MAX_COIN 100

// 动态规划函数，dp[i]表示最小需要的硬币数来支付i元
int coinChange(int coins[], int n, int amount) {
    // 初始化动态规划表
    int dp[MAX_COIN + 1];
    for (int i = 0; i <= amount; i++) {
        dp[i] = i; // 如果没有足够的钱，就直接返回当前金额
    }

    // 使用滚动数组优化空间复杂度
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < n && coins[j] <= i; j++) { 
            dp[i] = min(dp[i], dp[i - coins[j]] + 1); // 更新如果选择当前面额的最优情况
        }
    }

    return dp[amount]; // 返回找零所需的最小硬币数
}

int main() {
    int coins[] = {1, 2, 5}; // 面额数组
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 11; // 需要支付的金额
    int result = coinChange(coins, n, amount);

    if (result == amount) {
        printf("无法找零\n");
    } else {
        printf("最少需要 %d 枚硬币\n", result);
    }
    return 0;
}

在这个例子中，`coinChange`函数通过遍历所有可能的面额组合来找出最佳方案。它先假设没有硬币（即每个金额都是它本身），然后逐步尝试加入更大的面额，直到达到目标金额为止。