第19章_贪心算法

授课语音

贪心算法的实现步骤

1. 贪心策略的设计

贪心算法的核心在于如何设计每一步的选择标准，即贪心策略。在每个决策点，贪心算法选择当前最优的选项，并期望通过一系列局部最优的选择，最终得到全局最优解。

设计贪心策略时需要解决的两个关键问题：

如何定义每一步的选择标准？
- 例如，在活动选择问题中，我们选择结束时间最早的活动。在找零问题中，我们选择面额最大的硬币。
如何确保每一步选择的局部最优解能推导出全局最优解？
- 即确保贪心选择的方式不“错过”更好的解。

贪心算法的成功依赖于问题是否满足贪心选择性质，即每次局部最优解能最终构成全局最优解。如果问题符合此性质，贪心算法能保证找到最优解；否则，贪心算法可能无法得到正确的解。

2. 贪心算法的步骤

贪心算法的实现可以通过以下几个步骤来完成：

步骤 1：定义贪心策略

首先，我们需要明确每一步选择的标准，也就是贪心选择。例如：

在活动选择问题中，每次选择结束时间最早的活动。
在找零问题中，每次选择面额最大的硬币。

贪心策略的设计决定了算法的正确性与效率。

步骤 2：迭代过程

一旦贪心选择标准确定，我们可以进入迭代过程：

在每一轮中，基于当前状态做出最优选择。
更新状态并继续进行下一轮选择。

例如，在活动选择问题中，我们从第一个活动开始，选择最早结束的活动。然后，在剩余活动中选择下一个最早结束的活动，直到所有活动被处理完或不再有符合条件的活动。

步骤 3：验证最优性

为了确保贪心算法得到的解是正确的，我们需要验证每一步的局部最优解是否构成了全局最优解。这通常通过数学证明来完成。

常见的证明方法有：

交换证明法：通过假设最优解不符合贪心选择条件，然后通过交换操作将其转化为符合贪心选择的解。
反证法：通过假设某个解不符合贪心算法的选择标准，推导出矛盾，从而证明贪心算法的选择是最优的。

关键：贪心算法并不适用于所有问题

并不是所有问题都符合“贪心选择性质”。贪心算法适用于那些局部最优解能够推导出全局最优解的问题。如果一个问题不能满足这一性质，则贪心算法可能会得到错误的解。

3. 贪心算法的证明

对于贪心算法来说，证明其正确性是关键步骤。通常使用以下两种常见的证明方法：

1. 交换证明法

交换证明法是通过假设某一最优解不符合贪心选择的条件，之后通过交换一些元素，将其转换为符合贪心选择的解，从而证明贪心算法的正确性。例如，在活动选择问题中，假设某个解不是最优的，通过交换其中不符合贪心策略的活动，最终得到一个符合贪心策略的最优解。

2. 反证法

反证法通过假设某个解不符合贪心算法的选择标准，然后推导出矛盾，证明贪心选择是最优的。例如，如果我们假设贪心算法选择了错误的活动，我们可以通过推导出不合逻辑的结论，证明贪心选择是正确的。

4. 贪心算法中的常见陷阱

尽管贪心算法在许多问题中表现优异，但它并不适用于所有问题。贪心算法的局限性之一是它可能无法得到最优解，特别是在不符合贪心选择性质的问题中。

常见问题

找零问题：
- 假设我们希望用最少的硬币数量来凑一个给定的金额。贪心算法会选择面额最大的硬币，但在某些情况下，选择面额最大的硬币并不能得到最优解。
分糖果问题：
- 假设我们希望以最低的总费用分配糖果，每个孩子要求的糖果数量不同，而糖果有不同的包装和价格。贪心算法可能选择便宜的糖果，但由于缺乏全局考量，可能导致总费用不是最优的。

解决方法

在使用贪心算法前，我们需要确保问题符合贪心选择性质。若问题不符合，可以考虑其他算法，如动态规划或回溯算法。

5. 代码案例（Java）

例：活动选择问题

活动选择问题是贪心算法的经典应用。给定多个活动，每个活动有开始时间和结束时间，要求选择尽可能多的不重叠活动。

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

public class ActivitySelection {
    // 定义活动类，包含开始时间和结束时间
    static class Activity {
        int start;
        int finish;
    }

    public static void main(String[] args) {
        Activity[] activities = new Activity[5];
        // 输入活动的开始时间和结束时间
        activities[0] = new Activity();
        activities[0].start = 1;
        activities[0].finish = 3;
        
        activities[1] = new Activity();
        activities[1].start = 2;
        activities[1].finish = 5;

        activities[2] = new Activity();
        activities[2].start = 4;
        activities[2].finish = 6;

        activities[3] = new Activity();
        activities[3].start = 6;
        activities[3].finish = 8;

        activities[4] = new Activity();
        activities[4].start = 5;
        activities[4].finish = 7;

        // 按照结束时间排序活动
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        // 选择活动
        int lastFinishTime = 0; // 上一个被选择活动的结束时间
        System.out.println("选择的活动有：");
        for (int i = 0; i < activities.length; i++) {
            if (activities[i].start >= lastFinishTime) {
                System.out.println("活动[" + activities[i].start + ", " + activities[i].finish + "]");
                lastFinishTime = activities[i].finish;
            }
        }
    }
}

代码解释：

活动类：定义了一个 Activity 类，用来存储每个活动的开始时间和结束时间。
排序：活动数组按结束时间进行排序，这样我们就可以选择结束时间最早的活动。
选择活动：从第一个活动开始选择，然后逐个遍历剩余活动，只要活动的开始时间不早于当前已选择活动的结束时间，就可以选择这个活动。

输出：

选择的活动有：
活动[1, 3]
活动[4, 6]
活动[6, 8]

通过贪心算法，我们成功选出了最大数量的不重叠活动。

6. 总结

贪心算法是通过局部最优选择推导出全局最优解的有效方法，但它并非适用于所有问题。使用贪心算法前，必须确认问题符合贪心选择性质。设计贪心策略时，需要保证每一步的局部最优解能累积为全局最优解。对于不符合贪心性质的问题，可以考虑其他更复杂的算法，如动态规划、回溯算法等。

去1:1私密咨询

系列课程：

免费

VIP会员

第2课_贪心算法的实现步骤