给定数量限制的多面额硬币组合找零算法实现求助

我来帮你搞定这个硬币凑数的问题！你现在的需求是用给定数量的100、50、25、10分硬币凑出指定金额x，不需要找最少硬币的最优解，只要找到任意一种可行组合就行。你的现有代码只在部分场景有效，大概率是没考虑硬币数量限制和遍历逻辑的问题，我给你梳理一个简单可靠的思路，再把代码补全修正。

核心思路（贪心策略适配数量限制） #

因为不需要最优解，我们可以用从大到小遍历硬币面值的贪心思路，同时严格遵守每种硬币的可用数量：

• 优先用面值大的硬币，尽可能多取（但不能超过该硬币的剩余数量，也不能超过剩余金额能容纳的数量）
• 每取完一种硬币，更新剩余金额和已用硬币数量
• 遍历完所有硬币后，检查剩余金额是否为0：如果是，说明找到有效组合；否则就是无法凑出目标金额

修正后的完整代码 #

#include <stdio.h>

// 定义硬币结构体：面值+可用数量
struct coins {
    int valor;  // 硬币面值
    int quant;  // 可用数量
};

int main() {
    int x;  // 目标金额
    printf("请输入目标金额：");
    scanf("%d", &x);
    int remaining = x;  // 剩余需要凑的金额

    // 初始化可用硬币：按面值从大到小排序（关键！）
    struct coins available_coins[4] = {
        {100, 2},  // 示例：2个100分硬币
        {50, 3},   // 3个50分硬币
        {25, 5},   // 5个25分硬币
        {10, 10}   // 10个10分硬币
    };
    int changecoins[4] = {0};  // 记录每种硬币的使用数量

    // 遍历每种硬币
    for (int i = 0; i < 4; i++) {
        if (remaining <= 0) break;  // 已经凑够，提前退出

        // 计算当前硬币最多能取的数量：取两者最小值
        int take = remaining / available_coins[i].valor;
        take = take > available_coins[i].quant ? available_coins[i].quant : take;

        changecoins[i] = take;
        remaining -= take * available_coins[i].valor;
    }

    // 检查是否成功凑出目标金额
    if (remaining == 0) {
        printf("成功凑出%d分，组合为：\n", x);
        for (int i = 0; i < 4; i++) {
            if (changecoins[i] > 0) {
                printf("%d个%d分硬币\n", changecoins[i], available_coins[i].valor);
            }
        }
    } else {
        printf("无法用给定硬币凑出%d分\n", x);
    }

    return 0;
}

关键细节说明 #

• 硬币排序：一定要按面值从大到小排列，这样贪心策略才能快速凑出金额，避免小面值先用完导致大面值无法利用的情况（比如要凑150分，如果先拿10分硬币，可能把10分用完了，但其实用1个100+1个50更简单）
• 数量限制处理：take的计算要同时考虑剩余金额能容纳的数量和硬币的可用数量，不能只取其中一个
• 提前退出：当剩余金额为0时，直接跳出循环，没必要继续遍历剩下的硬币

测试场景示例 #

比如目标金额是275分，可用硬币是示例中的数量：

• 先取2个100分（用掉200，剩余75）
• 再取1个50分（用掉50，剩余25）
• 再取1个25分（用掉25，剩余0）
• 最终组合是2个100+1个50+1个25，完美凑出

如果目标金额是30分，但可用的25分硬币数量为0：

• 会取3个10分硬币，同样能成功凑出

如果目标金额是5分，那所有硬币都无法凑出，会提示无法完成

内容的提问来源于stack exchange，提问作者Linx