C++实现贪心算法解决超市找零问题

### 💡贪心算法超市找零问题分析 贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法。在超市找零问题中，目标是用最少数量的硬币来完成找零。为了实现这一目标，每次都选择面值最大且不超过剩余找零金额的硬币，直到找零完成。 ### 📝C++代码实现 ```cpp #include <iostream> #include <vector> // 找零函数 std::vector<int> coinChange(int amount) { // 定义硬币面值，按从大到小排序 std::vector<int> coinValues = {25, 10, 5, 1}; std::vector<int> result; // 遍历每种硬币面值 for (int coin : coinValues) { // 计算当前面值硬币的使用数量 while (amount >= coin) { result.push_back(coin); amount -= coin; } } return result; } int main() { int amount = 63; // 假设需要找零63美分 std::vector<int> change = coinChange(amount); std::cout << "找零的硬币组合为: "; for (int coin : change) { std::cout << coin << " "; } std::cout << std::endl; return 0; } ``` ### 📚代码解释 1. **定义硬币面值**：`coinValues` 数组存储了可用的硬币面值，按从大到小的顺序排列。 2. **遍历硬币面值**：在 `coinChange` 函数中，遍历每种硬币面值，对于每种面值，只要剩余找零金额大于等于该面值，就使用该面值的硬币，并更新剩余找零金额。 3. **存储结果**：将使用的硬币面值存储在 `result` 向量中。 4. **主函数**：在 `main` 函数中，调用 `coinChange` 函数进行找零，并输出找零的硬币组合。 ### ⚠️注意事项 - 该算法假设硬币面值是固定的，并且可以无限供应。 - 贪心算法并不一定能得到全局最优解，在某些情况下，可能存在更优的找零方案。例如，当硬币面值为 `{1, 3, 4}`，需要找零 6 时，贪心算法会选择 `4 + 1 + 1`，而最优解是 `3 + 3`。 ######[AI问答 | 601点数解答 | 2026-03-28 16:07:03]