贪心算法详解及Java实现

1. 什么是贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致全局最优解的算法策略。它不像动态规划那样考虑所有可能的子问题，而是做出局部最优选择，期望这些选择能导致全局最优解。

2. 贪心算法的基本特性

• 贪心选择性质：每一步的最优选择都能导致最终的全局最优解
• 最优子结构：问题的最优解包含其子问题的最优解
• 不可回退：一旦做出选择就不能改变

3. 贪心算法的基本步骤

1. 将问题分解为若干个子问题
2. 对每个子问题求解局部最优解
3. 将局部最优解合并为原问题的一个解

4. 经典贪心算法问题及Java实现

4.1 找零钱问题

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CoinChange {
    public static List<Integer> greedyCoinChange(int amount, List<Integer> coins) {
        // 将硬币面额从大到小排序
        coins.sort(Collections.reverseOrder());
        List<Integer> result = new ArrayList<>();
        
        for (int coin : coins) {
            while (amount >= coin) {
                amount -= coin;
                result.add(coin);
            }
        }
        
        if (amount != 0) {
            System.out.println("无法正好找零");
            return new ArrayList<>();
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        List<Integer> coins = Arrays.asList(1, 2, 5, 10, 20, 50, 100);
        int amount = 93;
        
        List<Integer> change = greedyCoinChange(amount, coins);
        System.out.println("找零" + amount + "元需要的硬币为：" + change);
    }
}

4.2 活动选择问题

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Activity {
    int start;
    int end;
    
    public Activity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class ActivitySelection {
    public static List<Activity> selectActivities(List<Activity> activities) {
        // 按照结束时间排序
        activities.sort(Comparator.comparingInt(a -> a.end));
        
        List<Activity> selected = new ArrayList<>();
        selected.add(activities.get(0));
        int lastEnd = activities.get(0).end;
        
        for (int i = 1; i < activities.size(); i++) {
            if (activities.get(i).start >= lastEnd) {
                selected.add(activities.get(i));
                lastEnd = activities.get(i).end;
            }
        }
        
        return selected;
    }
    
    public static void main(String[] args) {
        List<Activity> activities = new ArrayList<>();
        activities.add(new Activity(1, 4));
        activities.add(new Activity(3, 5));
        activities.add(new Activity(0, 6));
        activities.add(new Activity(5, 7));
        activities.add(new Activity(3, 8));
        activities.add(new Activity(5, 9));
        activities.add(new Activity(6, 10));
        activities.add(new Activity(8, 11));
        activities.add(new Activity(8, 12));
        activities.add(new Activity(2, 13));
        activities.add(new Activity(12, 14));
        
        List<Activity> result = selectActivities(activities);
        System.out.println("选择的活动序列为：");
        for (Activity act : result) {
            System.out.print("[" + act.start + ", " + act.end + "] ");
        }
    }
}

4.3 背包问题（分数背包）

import java.util.Arrays;
import java.util.Comparator;

class Item {
    int weight;
    int value;
    
    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

public class FractionalKnapsack {
    public static double getMaxValue(int capacity, Item[] items) {
        // 按单位价值从高到低排序
        Arrays.sort(items, new Comparator<Item>() {
            @Override
            public int compare(Item a, Item b) {
                double ratioA = (double) a.value / a.weight;
                double ratioB = (double) b.value / b.weight;
                return Double.compare(ratioB, ratioA);
            }
        });
        
        double totalValue = 0.0;
        
        for (Item item : items) {
            if (capacity >= item.weight) {
                capacity -= item.weight;
                totalValue += item.value;
            } else {
                double fraction = (double) capacity / item.weight;
                totalValue += item.value * fraction;
                break;
            }
        }
        
        return totalValue;
    }
    
    public static void main(String[] args) {
        int capacity = 50;
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        
        double maxValue = getMaxValue(capacity, items);
        System.out.println("背包能装的最大价值为：" + maxValue);
    }
}

5. 贪心算法的适用场景

1. 可以分解为子问题的问题：如活动选择问题
2. 具有贪心选择性质的问题：如霍夫曼编码
3. 需要近似解的问题：当精确解计算成本过高时

6. 贪心算法的局限性

1. 不能保证全局最优：只在特定条件下能得到最优解
2. 需要证明正确性：必须证明贪心选择能得到最优解
3. 适用范围有限：不是所有问题都适用贪心策略

7. 贪心算法与动态规划的比较

特性	贪心算法	动态规划
最优解保证	不一定全局最优	保证全局最优
计算复杂度	通常较低	通常较高
子问题	不保存子问题解	保存子问题解
决策	不可回退	可以考虑所有可能性
适用问题	具有贪心选择性质的问题	具有最优子结构的问题

8. 实际应用案例

1. 网络路由：Dijkstra算法求最短路径
2. 数据压缩：霍夫曼编码
3. 任务调度：CPU任务调度算法
4. 最小生成树：Prim和Kruskal算法
5. 集合覆盖问题：如广播台覆盖问题

9. 如何设计贪心算法

1. 问题分析：确定问题是否具有贪心选择性质
2. 贪心策略设计：确定每一步的最优选择标准
3. 正确性证明：证明贪心选择能得到全局最优解
4. 算法实现：编写代码实现贪心策略
5. 效率分析：分析算法的时间和空间复杂度

10. 总结

贪心算法是一种简单高效的算法设计范式，适用于具有贪心选择性质的问题。虽然它不能解决所有优化问题，但在适用场景下能提供高效的解决方案。理解贪心算法的原理和实现方式，对于解决实际编程问题具有重要意义。

在Java中实现贪心算法时，可以利用Collections.sort()或Arrays.sort()进行排序，结合适当的比较器来制定贪心策略。通过练习经典贪心问题，可以更好地掌握这一算法思想。

关键点总结：

• 贪心算法做出局部最优选择期望得到全局最优
• 必须验证问题是否具有贪心选择性质
• Java实现时注意排序和比较器的使用
• 适用于活动选择、背包问题、最短路径等问题
• 比动态规划更高效但适用范围更窄