贪心算法——c#

贪心算法通俗解释

贪心算法是一种"每一步都选择当前最优解"的算法策略。它不关心全局是否最优，而是通过局部最优的累积来逼近最终解。优点是简单高效，缺点是可能无法得到全局最优解。

一句话秒懂

自动售货机找零钱：用最少数量的硬币凑出指定金额。比如找零198美分，它会优先用25美分的大硬币，不够再用小的，直到凑够金额。

---

背景故事

想象你在加拿大超市当收银员（CAD场景）：

1. 顾客买了东西

2. 你需要快速找出零钱198分

3. 收银台硬币有：50分、25分、10分、5分、1分

4. 目标：用最少的硬币数量凑出1300分

using System;
using System.Collections.Generic;public class GreedyAlgorithm
{[CommandMethod("xx")]public static void 贪心算法之硬币找零(){// 场景模拟：在 CAD 系统中自动计算最优找零方案List<int> coins = new List<int> { 1, 5, 10, 25,50 }; // 硬币面额（美分）int amount = 198; // 需要找零的金额（美分）List<int> result = CoinChange(coins, amount);Env.Editor.WriteMessage($"找零 {amount} 美分需要的最少硬币：");foreach (int coin in result){Env.Editor.WriteMessage(coin + " "); }}/// <summary>/// 贪心算法实现硬币找零/// </summary>/// <param name="coins">可用硬币面额数组</param>/// <param name="amount">目标金额</param>/// <returns>硬币组合列表</returns>static List<int> CoinChange(List<int> coins, int amount){var sortCoins = coins.OrderByDescending(x=>x).ToList();// Array.Sort(coins, (a, b) => b.CompareTo(a)); // 降序排序（关键贪心步骤）List<int> change = new List<int>();foreach (int coin in sortCoins){while (amount >= coin){// 在 CAD 系统中，这里可以记录交易日志change.Add(coin);amount -= coin;}}return change;}
}

 

代码注释说明：

1. Array.Sort(coins, (a, b) => b.CompareTo(a))
   将硬币按面额从大到小排序，这是贪心算法的核心——优先使用大面额硬币

2. while (amount >= coin)
   只要当前硬币可以用就持续使用，体现贪心的"局部最优"特性

3. 时间复杂度为 O(n log n)，主要来自排序操作

4. 贪心算法特点总结

   特性	说明
   优点	实现简单，运行效率高
   缺点	不一定得到全局最优解
   适用场景	问题具有贪心选择性质
   CAD 应用场景	路径规划、元件布局、自动布线等