贪心算法实现硬币找零问题C++

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，希望导致结果是全局最好或最优的策略。在硬币找零问题（Coin Change Problem）中，给定一组面额，我们要找出最小的硬币组合来凑够一个目标金额。

在C++中，可以使用动态规划结合贪心思想解决这个问题。首先定义一个二维数组dp，其中dp[i]表示找零i所需的最小硬币数。然后按照从大到小的面额顺序遍历：

1. 初始化所有dp值为无穷大，除了dp[0]=0，因为0元不需要硬币。
2. 对于每个面额j，如果目标金额i大于等于j，则更新dp[i]，取dp[i]和dp[i-j]+1中的较小者，即保留原有的方案或是加上一枚面额j的硬币。
3. 当遍历完所有面额后，dp[target]就是最小的硬币组合数。

以下是简单的C++代码示例：

#include <vector>
using namespace std;

int coinChange(vector<int>& coins, int target) {
    vector<int> dp(target + 1, INT_MAX); // dp数组初始化为无穷大
    dp[0] = 0; // 目标金额为0的情况，无需硬币

    for (int i = 1; i <= target; ++i) { // 遍历目标金额
        for (int j : coins) { // 遍历硬币面额
            if (j <= i && dp[i - j] != INT_MAX) { // 如果足够支付，尝试减去并更新dp
                dp[i] = min(dp[i], dp[i - j] + 1);
            }
        }
    }

    return dp[target] == INT_MAX ? -1 : dp[target]; // 返回最小硬币数，找不到组合则返回-1
}