贪心算法——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 应用场景	路径规划、元件布局、自动布线等