改进贪心硬币找零算法：修复C++实现的最优解失效问题

你遇到的问题非常典型——贪心算法在硬币找零中只适用于规范面额体系（比如我们常用的1、5、10、20这种，每个大面额的设计能保证贪心选择的最优性），但像{1,6,9}这种非规范面额集合，贪心“每次选最大面额”的策略就会错过更优的组合。

为什么你的当前代码失效？ #

你的代码逻辑是从最大面额开始尽可能多取，对于30元的场景：

• 先取3个9元（共27元），剩下3元只能用3个1元凑，总共6枚硬币
• 但最优解是2个6元 + 2个9元 = 30元，仅需4枚硬币
  贪心没法预判“少拿一个9元，换成两个6元”能减少总数量，所以需要用动态规划来枚举所有可能的组合，找到最优解。

改进方案：动态规划实现最优找零 #

下面是基于动态规划的C++实现，它能正确处理所有面额场景，返回硬币数量最少的组合：

#include <vector>
#include <algorithm>
#include <climits>

std::vector<int> get_change(const std::vector<int>& denominations, int amount) {
    // 第一步：计算最少硬币数的dp数组
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0; // 凑0元需要0枚硬币

    for (int i = 1; i <= amount; ++i) {
        for (int denom : denominations) {
            if (denom <= i && dp[i - denom] != INT_MAX) {
                dp[i] = std::min(dp[i], dp[i - denom] + 1);
            }
        }
    }

    // 如果dp[amount]还是INT_MAX，说明无法凑出该金额（这里假设面额包含1，所以不会出现）
    if (dp[amount] == INT_MAX) {
        return {};
    }

    // 第二步：回溯找到具体的硬币组合
    std::vector<int> result;
    int remaining = amount;
    while (remaining > 0) {
        for (int denom : denominations) {
            if (denom <= remaining && dp[remaining - denom] == dp[remaining] - 1) {
                result.push_back(denom);
                remaining -= denom;
                break;
            }
        }
    }

    // 可选：对结果排序（如果需要和原贪心输出一样的升序顺序）
    std::sort(result.begin(), result.end());
    return result;
}

代码说明 #

1. DP数组初始化：dp[i]存储凑成金额i所需的最少硬币数，初始时除了dp[0]为0，其他都设为无穷大（表示暂时无法凑出）。
2. DP数组更新：遍历每个金额，对每个面额，如果当前面额不超过金额，且凑出i-denom的硬币数存在，就更新dp[i]为更小的值。
3. 回溯找组合：从目标金额倒推，找到每个步骤中使用的面额，直到金额减为0，这样就能得到具体的硬币组合。

测试示例 #

调用get_change({1,6,9}, 30)时，返回的结果是{6,6,9,9}（排序后），正好是最优解，硬币数量仅为4枚。

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