贪心算法 | 小菜鸟

贪心算法：局部最优到全局近似的智慧

贪心算法是一种通过每步选择局部最优解来寻求全局最优解的启发式算法。它不追求完美，而是在有限步骤内快速找到近似最优解，广泛应用于资源分配、路径规划等场景。本文通过经典案例解析其原理、特性及适用边界。

贪心算法的核心思想

核心原则

局部最优：每一步都选择当前状态下最优的选项（如价值最高、成本最低）。
无回溯：一旦做出选择，不再修改，直接进入下一步。
全局近似：通过累积局部最优解，最终得到接近全局最优的结果（未必是真正最优）。

与其他算法的区别

与动态规划：动态规划会保存中间结果并回溯调整，确保全局最优；贪心算法无回溯，效率更高但可能非最优。
与穷举法：穷举法遍历所有可能，结果最优但效率极低；贪心算法通过启发式选择减少计算量。

经典案例：背包问题中的贪心策略

问题描述

小偷的背包最大承重为 35 磅，可偷取的物品如下：

音响：30 磅，3000 元
笔记本电脑：20 磅，2000 元
吉他：15 磅，1500 元

目标：装入背包的物品总价值最高。

贪心算法的解题步骤

排序策略：按 “单位重量价值” 从高到低排序（或直接按总价值排序，视场景而定）。
本例按总价值排序：音响（3000 元）→ 笔记本电脑（2000 元）→ 吉他（1500 元）。
逐步选择：
- 第一步：选价值最高的音响（30 磅），剩余承重 5 磅（35-30）。
- 第二步：剩余承重无法装下笔记本电脑（20 磅）或吉他（15 磅），结束。
结果：总价值 3000 元（仅音响）。

算法局限

贪心算法得到的并非最优解：

最优解应为 “笔记本电脑 + 吉他”（20+15=35 磅，总价值 3500 元）。
原因：贪心算法仅关注局部最优（单步最高价值），忽略了组合后的全局最优。

代码实现

import java.util.*;

public class KnapsackGreedy {
    // 物品类
    static class Goods implements Comparable<Goods> {
        String name;
        int weight;
        int value;

        public Goods(String name, int weight, int value) {
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        // 按价值从高到低排序
        @Override
        public int compareTo(Goods other) {
            return Integer.compare(other.value, this.value); // 逆序
        }
    }

    public static void main(String[] args) {
        Goods[] goods = {
            new Goods("音响", 30, 3000),
            new Goods("笔记本电脑", 20, 2000),
            new Goods("吉他", 15, 1500)
        };
        int maxWeight = 35;

        // 排序：价值从高到低
        Arrays.sort(goods);

        int currentWeight = 0;
        int totalValue = 0;
        Set<String> selected = new HashSet<>();

        // 贪心选择
        for (Goods g : goods) {
            if (currentWeight + g.weight <= maxWeight) {
                currentWeight += g.weight;
                totalValue += g.value;
                selected.add(g.name);
            }
        }

        System.out.println("选中物品：" + selected);
        System.out.println("总价值：" + totalValue + "元");
    }
}

输出：

选中物品：[音响]
总价值：3000元

贪心算法的适用场景

贪心算法仅在满足 “贪心选择性质” 时才能得到全局最优解，即：
局部最优选择的累积结果必然是全局最优。

典型适用场景

哈夫曼编码：通过优先合并频率最低的节点，生成最优前缀码。
活动选择问题问题 **：选择最多不重叠的活动（如会议安排），按结束时间排序后贪心选择。
零钱兑换：用最少硬币凑金额（适用于面额为 “贪心友好” 的货币体系，如人民币）。
最小生成树：Prim 算法和 Kruskal 算法均通过贪心策略选择边，构建最小总权重树。

不适用场景

问题存在 “后效性”：即当前选择会影响未来选择的最优性（如背包问题、最长路径问题）。
需全局统筹才能最优的最优的场景（如旅行商问题 TSP）。

贪心算法的优缺点

优点

效率高：时间复杂度通常为 O (nlogn)（主要来自排序），远低于动态规划或穷举法。
实现简单：无需复杂的状态记录和回溯，逻辑直观。

缺点

未必最优：仅在特定问题中得到全局最优，多数情况下是近似解。
对排序策略敏感：不同的贪心准则（如按价值、按单位价值）可能导致结果差异较大