贪默算法——c#

贪默算法普通表明

贪默算法是一种"每一步都选择当前最优解"的算法战略。它不关心全局是否最优，而是通过局部最优的累积来迫近终极解。长处是简朴高效，缺点是大概无法得到全局最优解。
一句话秒懂

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

---

配景故事

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

•         顾客买了东西
  
•         你须要快速找出零钱198分
  
•         收银台硬币有：50分、25分、10分、5分、1分
  
•         目的：用最少的硬币数量凑出198分
  

2. using System;
3. using System.Collections.Generic;
5. public class GreedyAlgorithm
6. {
7.     [CommandMethod("xx")]
8.    public static void 贪心算法之硬币找零()
9.     {
10.         // 场景模拟：在 CAD 系统中自动计算最优找零方案
11.        List<int> coins = new List<int> { 1, 5, 10, 25,50 }; // 硬币面额（美分）
12.         int amount = 198; // 需要找零的金额（美分）
14.         List<int> result = CoinChange(coins, amount);
16.         Env.Editor.WriteMessage($"找零 {amount} 美分需要的最少硬币：");
17.         foreach (int coin in result)
18.         {
19.             Env.Editor.WriteMessage(coin + " ");
20.         }
21.     }
23.     /// <summary>
24.     /// 贪心算法实现硬币找零
25.     /// </summary>
26.     /// <param name="coins">可用硬币面额数组</param>
27.     /// <param name="amount">目标金额</param>
28.     /// <returns>硬币组合列表</returns>
29.     static List<int> CoinChange(List<int> coins, int amount)
30.     {
31.         var sortCoins = coins.OrderByDescending(x=>x).ToList();
32.        // Array.Sort(coins, (a, b) => b.CompareTo(a)); // 降序排序（关键贪心步骤）
33.         List<int> change = new List<int>();
35.         foreach (int coin in sortCoins)
36.         {
37.             while (amount >= coin)
38.             {
39.                 // 在 CAD 系统中，这里可以记录交易日志
40.                 change.Add(coin);
41.                 amount -= coin;
42.             }
43.         }
45.         return change;
46.     }
47. }

复制代码

 
代码表明阐明：

•         Array.Sort(coins, (a, b) => b.CompareTo(a))
          将硬币按面额从大到小排序，这是贪默算法的焦点——优先使用大面额硬币
  
•         while (amount >= coin)
          只要当前硬币可以用就一连使用，体现贪婪的"局部最优"特性
  
•         时间复杂度为 O(n log n)，重要来自排序操纵
  
•         贪默算法特点总结
  
          特性阐明长处实现简朴，运行服从高缺点不肯定得到全局最优解实用场景题目具有贪婪选择性子CAD 应用场景路径规划、元件结构、自动布线等