- C++
看完上面三段话,就明白了什么是贪心算法了
- @ 2025-12-11 20:08:11
贪心算法就像小朋友分糖果时的“简单办法”:每次只做当下看起来最好的选择,不考虑以后,最后慢慢凑出结果。
举个例子:
如果妈妈让你用最少的硬币凑出3元,硬币有1元、5角、1角。
贪心的做法就是:先拿最大的1元硬币(拿3个就够了),而不是先拿一堆1角的。这样一步一步选当前最大的、最省事的,最后用的硬币数量肯定最少。
再比如:
放学回家想走最少的路,路口时先选眼前最近的那条路,一直这么选,最后可能就到家了(虽然不一定是绝对最短,但简单好操作)。
总结:贪心算法就是“走一步看一步,每次挑最好的”,像小朋友做选择一样直接,适合解决一些简单的分配、挑选问题~
贪心算法的解题过程就像小朋友解决“分零食”“选路线”这类问题时的思路,简单来说就是三步:定规则→按规则选→凑结果。用具体例子来讲更清楚:
例子:用最少的硬币凑1元5角(硬币有1元、5角、1角)
第一步:定“贪心规则”
先想清楚“当下最好的选择”是什么。这里要“硬币数量最少”,所以规则就是:每次都拿面值最大的硬币(因为大面值硬币能更快凑够钱,用的数量少)。
第二步:按规则一步步选
- 总目标是1元5角,当前最大的硬币是1元,拿1个(剩下5角);
- 剩下5角,当前最大的硬币是5角,拿1个(刚好凑够)。
第三步:凑出结果
一共拿了“1元+5角”,共2个硬币,这就是最少的数量。
总结贪心算法的解题步骤:
- 找“贪心策略”:确定每次选择的“最优标准”(比如选最大、最小、最近的);
- 逐步选择:按照策略,每次选一个当前最好的,缩小问题范围;
- 检查结果:看看这样选出来的结果是否符合要求(比如是否真的是最少、最短)。
就像小朋友分蛋糕,每次先拿最大的一块,最后每个人拿到的总和就是按这个简单规则分出来的结果~ 不过要注意,不是所有问题都能用贪心算法,只有当“每次选最好的,最后结果也是最好的”时才适用哦!
贪心算法的核心是每一步都做出当前局部最优的选择,期望最终得到全局最优解。它在代码中的体现往往围绕「规则定义(比如比大小)」「排序(为贪心选择铺路)」「遍历(逐步执行贪心策略)」这三个核心动作展开。
0 条评论
目前还没有评论...