C语言算法问答集：攻克贪心算法-C++-PHP中文网

C语言算法问答集：攻克贪心算法

WBOY

发布： 2024-10-09 09:15:02

原创

788人浏览过

本篇探索了贪心算法的原理和 c 语言实战应用。采用贪心找零示例，解释了如何从大到小枚举硬币面额，并尽量使用当前面额内的硬币找零。此外，还提供了背包问题、调度问题和活动选择问题等其他实战案例，展示了贪心算法在不同场景下的应用。尽管贪心算法不一定能产生全局最优解，但在许多情况下它能提供良好的近似解。

C语言算法问答集：攻克贪心算法

贪心算法：C 语言实战解析

贪心算法是一种常用的算法技术，它关注于在当前阶段做出局部最优选择，以达到全局最优或近似最优解。本篇文章将通过 C 语言实战案例，深入讲解贪心算法的原理和应用。

实例：贪心找零

立即学习“C语言免费学习笔记（深入）”；

目标：给定一个金额和一组硬币面额，求出使用最少的硬币找零的方案。

代码：

#include <stdio.h>
#include <stdlib.h>

// 存放所有硬币面额
int coins[] = {1, 5, 10, 25, 50, 100};
// 枚举硬币面额种类
int n = sizeof(coins) / sizeof(coins[0]);

// 贪心算法找零
int greedy_change(int amount) {
    int num_coins = 0;
    // 遍历硬币面额从大到小
    for (int i = n - 1; i >= 0; i--) {
        // 在当前硬币面额范围内取尽可能多的硬币
        while (amount >= coins[i]) {
            amount -= coins[i];
            num_coins++;
        }
    }

    // 返回所需硬币数量
    return num_coins;
}

// 主函数
int main() {
    // 设置要找零的金额
    int amount = 123;

    // 调用贪心算法找零
    int num_coins = greedy_change(amount);

    // 输出结果
    printf("最少的硬币数量：%d\n", num_coins);

    return 0;
}

登录后复制

代码讲解：