C#贪心算法

贪心算法：生活与代码中的 “最优选择大师”

在生活里，我们常常面临各种选择，都希望能做出最有利的决策。比如在超市大促销时，面对琳琅满目的商品，你总想用有限的预算买到价值最高的东西。贪心算法，就像是一个精明的生活顾问，总能在每一步都做出当下看起来最优的选择，帮我们在各种场景中找到 “最优解”。

贪心算法原理：目光短浅却很高效

贪心算法遵循一种 “今朝有酒今朝醉” 的策略，在对问题求解时，总是做出在当前看来是最好的选择。它并不从整体最优上加以考虑，所做出的仅仅是在某种意义上的局部最优解。但神奇的是，在很多情况下，这些局部最优解最后能构成全局最优解。

想象你在一个布满金币的房间，规定只能拿一次，每次拿一枚。贪心算法会让你在每一次伸手时，都选择眼前最大的那枚金币，而不考虑未来可能出现更大金币的情况。虽然看起来有点 “目光短浅”，但在合适的问题中，这种策略能高效地解决问题。

应用场景及代码实现

活动安排问题：时间管理大师的秘诀

假设你是一个忙碌的职场人，一天内有多个会议要参加，每个会议都有开始时间和结束时间，你想参加尽可能多的会议，该怎么选择呢？这就是活动安排问题。

贪心算法的策略是：优先选择结束时间最早的会议，只要这个会议的开始时间晚于前一个已选择会议的结束时间，就把它加入日程。

using System;
using System.Collections.Generic;
using System.Linq;
class Activity
{
 public int Start { get; set; }
 public int End { get; set; }
 public Activity(int start, int end)
 {
 Start = start;
 End = end;
 }
}

class GreedyAlgorithm
{
 public static List<Activity> ActivitySelection(List<Activity> activities)
 {
 activities = activities.OrderBy(a => a.End).ToList();
 List<Activity> selectedActivities = new List<Activity>();
 selectedActivities.Add(activities[0]);
 int lastEnd = activities[0].End;
 for (int i = 1; i < activities.Count; i++)
 {
 if (activities[i].Start >= lastEnd)
 {
 selectedActivities.Add(activities[i]);
 lastEnd = activities[i].End;
 }
 }
 return selectedActivities;
 }
}

class Program
{
 static void Main()
 {
 List<Activity> activities = new List<Activity>
 {
 new Activity(1, 3),
 new Activity(2, 5),
 new Activity(4, 6),
 new Activity(5, 7),
 new Activity(7, 9)
 };
 List<Activity> selected = GreedyAlgorithm.ActivitySelection(activities);
 Console.WriteLine("选择的活动:");
 foreach (var activity in selected)
 {
 Console.WriteLine($"开始时间: {activity.Start}, 结束时间: {activity.End}");
 }
 }
}

找零问题：收银员的高效策略

当你去商店购物付款后，收银员需要找给你零钱。假设商店有各种面额的硬币和纸币，如何用最少的货币数量找零呢？

贪心算法的做法是：每次都优先选择面额最大的货币，直到找零金额为零。

using System;
using System.Collections.Generic;
class GreedyAlgorithm
{
 public static List<int> MakeChange(int amount, List<int> denominations)
 {
 denominations = denominations.OrderByDescending(d => d).ToList();
 List<int> change = new List<int>();
 foreach (int denomination in denominations)
 {
 while (amount >= denomination
 {
 amount -= denomination;
 change.Add(denomination);
 }
 }
 return change;
 }
}

class Program
{
 static void Main()
 {
 int amount = 63;
 List<int> denominations = new List<int> { 25, 10, 5, 1 };
 List<int> change = GreedyAlgorithm.MakeChange(amount, denominations);
 Console.WriteLine("找零方案:");
 foreach (int coin in change)
 {
 Console.Write(coin + " ");
 }
 }
}

背包问题（部分背包）：灵活的背包打包法

在背包问题中，有一个容量有限的背包和一些物品，每个物品有重量和价值。部分背包问题允许你选择物品的一部分放入背包，目标是使背包内物品的总价值最大。

贪心算法的思路是：计算每个物品的价值重量比，优先选择价值重量比高的物品放入背包，直到背包装满。

using System;
using System.Collections.Generic;
using System.Linq;
class Item
{
 public int Weight { get; set; }
 public int Value { get; set; }
 public double ValuePerWeight => (double)Value / Weight;
 public Item(int weight, int value)
 {
 Weight = weight;
 Value = value;
 }
}

class GreedyAlgorithm
{
 public static double FractionalKnapsack(int capacity, List<Item> items)
 {
 items = items.OrderByDescending(i => i.ValuePerWeight).ToList();
 double totalValue = 0;
 int currentWeight = 0;
 foreach (var item in items)
 {
 if (currentWeight + item.Weight <= capacity)
 {
 currentWeight += item.Weight;
 totalValue += item.Value;
 }
 else
 {
 int remainingCapacity = capacity - currentWeight;
 totalValue += item.ValuePerWeight * remainingCapacity;
 break;
 }
 }
 return totalValue;
 }
}

class Program
{
 static void Main()
 {
 int capacity = 50;
 List<Item> items = new List<Item>
 {
 new Item(10, 60),
 new Item(20, 100),
 new Item(30, 120)
 };
 double maxValue = GreedyAlgorithm.FractionalKnapsack(capacity, items);
 Console.WriteLine($"背包能装下的最大价值: {maxValue}");
 }
}

贪心算法虽然在很多场景下表现出色，但它并非万能的。它的正确性依赖于问题本身具有的贪心选择性质和最优子结构性质。在实际应用中，需要仔细分析问题，判断贪心算法是否适用。要是你还想了解贪心算法在其他领域的应用，或者对代码实现有疑问，欢迎随时和我交流。