贪心算法（Greedy Algorithm）是一种在每一步选择中都做出当前最优选择的算法，其目标是通过局部最优解构建全局最优解。贪心算法应用广泛，如最小生成树、哈夫曼编码、区间调度等问题，通常用于解决具有“最优子结构”和“贪心选择性”特性的优化问题。

贪心算法的核心思想

贪心算法的基本思想是在每一步骤中都做出局部最优的选择，以期最终得到全局最优解。与动态规划不同，贪心算法不考虑前后状态的关系，而是直接依据当前情况做出选择。

贪心算法的正确性依赖于两个重要性质：

1. 最优子结构：问题的全局最优解可以通过最优的子问题解构建。
2. 贪心选择性：每一步的局部最优解能导向全局最优解。

经典问题：活动选择问题

活动选择问题是典型的贪心算法问题之一。在给定的时间区间内，如何选择最多的活动，使得它们之间互不冲突？

问题描述

给定 n 个活动，每个活动都有一个开始时间 s[i] 和结束时间 f[i]。目标是选择尽可能多的活动，使得它们互不重叠。

贪心策略

每次选择最早结束的活动，因为这样可以留出更多的时间给后续活动，保证可以选择更多的活动。通过这个贪心策略，我们能够找到问题的最优解。

贪心算法实现

type Activity = { start: number, finish: number };

// 按照结束时间升序排序
function sortByFinishTime(activities: Activity[]): Activity[] {
    return activities.sort((a, b) => a.finish - b.finish);
}

// 贪心选择活动
function selectActivities(activities: Activity[]): Activity[] {
    const sortedActivities = sortByFinishTime(activities);
    const selected: Activity[] = [];

    let lastFinishTime = 0;
    for (const activity of sortedActivities) {
        if (activity.start >= lastFinishTime) {
            selected.push(activity);
            lastFinishTime = activity.finish;
        }
    }

    return selected;
}

// 示例活动
const activities: Activity[] = [
    { start: 1, finish: 4 },
    { start: 3, finish: 5 },
    { start: 0, finish: 6 },
    { start: 5, finish: 7 },
    { start: 3, finish: 8 },
    { start: 5, finish: 9 },
    { start: 6, finish: 10 },
    { start: 8, finish: 11 },
    { start: 8, finish: 12 },
    { start: 2, finish: 13 },
    { start: 12, finish: 14 },
];

const result = selectActivities(activities);
console.log('选择的活动:', result);

代码解析

1. sortByFinishTime 函数将活动按照结束时间从小到大排序，这有助于每次选择最早结束的活动。
2. selectActivities 函数通过迭代排序后的活动，使用贪心策略选择不重叠的活动，最终输出选择的活动列表。
3. 每当选择一个活动后，更新 lastFinishTime，确保下一个活动的开始时间不早于当前活动的结束时间。

输出示例

给定的活动集合为：

[{ start: 1, finish: 4 },
 { start: 3, finish: 5 },
 { start: 0, finish: 6 },
 { start: 5, finish: 7 },
 { start: 3, finish: 8 },
 { start: 5, finish: 9 },
 { start: 6, finish: 10 },
 { start: 8, finish: 11 },
 { start: 8, finish: 12 },
 { start: 2, finish: 13 },
 { start: 12, finish: 14 }]

贪心算法选择的活动为：

[{ start: 1, finish: 4 },
 { start: 5, finish: 7 },
 { start: 8, finish: 11 },
 { start: 12, finish: 14 }]

可以看到，贪心算法通过每次选择最早结束的活动，得到了最多的互不冲突的活动。

经典问题：分数背包问题

分数背包问题是另一个经典的贪心算法应用场景。与 0-1 背包问题不同，分数背包问题允许物品可以部分装入背包，从而使得总价值最大化。

问题描述

给定 n 件物品，每件物品具有重量 w[i] 和价值 v[i]。背包的总承重为 W，求在不超过背包承重的前提下，如何选择物品，使得物品的总价值最大化。允许将物品拆分。

贪心策略

对于分数背包问题，每次选择单位重量价值最高的物品或物品部分装入背包，这样可以最大化背包的总价值。

贪心算法实现

type Item = { weight: number, value: number };

// 按照单位重量的价值降序排序
function sortByValuePerWeight(items: Item[]): Item[] {
    return items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
}

// 分数背包问题贪心算法
function fractionalKnapsack(items: Item[], capacity: number): number {
    const sortedItems = sortByValuePerWeight(items);
    let totalValue = 0;
    let currentWeight = 0;

    for (const item of sortedItems) {
        if (currentWeight + item.weight <= capacity) {
            // 完整装入物品
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            // 装入部分物品
            const remainingCapacity = capacity - currentWeight;
            totalValue += (item.value / item.weight) * remainingCapacity;
            break;
        }
    }

    return totalValue;
}

// 示例物品
const items: Item[] = [
    { weight: 10, value: 60 },
    { weight: 20, value: 100 },
    { weight: 30, value: 120 },
];

const capacity = 50;
const maxValue = fractionalKnapsack(items, capacity);
console.log('背包可以装入的最大价值:', maxValue);

代码解析

1. sortByValuePerWeight 函数按单位重量的价值降序对物品进行排序，保证每次选择的物品都具有最高的单位价值。
2. fractionalKnapsack 函数使用贪心策略将物品或部分物品装入背包，直到背包的容量被耗尽或物品被装完。
3. 当背包的剩余容量无法装下完整的物品时，算法只装入部分物品，并计算其对应的价值。

输出示例

给定物品为：

[{ weight: 10, value: 60 },
 { weight: 20, value: 100 },
 { weight: 30, value: 120 }]

背包最大承重 50，贪心算法装入的最大价值为：

背包可以装入的最大价值: 240

在这里，算法先装入单位价值最高的物品，最终在承重量不足时装入部分物品，使得背包的总价值最大化。

贪心算法的局限性

贪心算法通常不能保证全局最优解，除非问题本身具有贪心选择性和最优子结构。例如，在 0-1 背包问题中，贪心策略无法保证得到最优解，因为不允许拆分物品，局部最优解不一定能导向全局最优解。