3.1 贪心算法

贪心算法是一种常见的解决优化问题的方法，通过每步选择当前看起来最优的选择，希望得到全局最优解。下面我将提供一些使用 Java 实现的贪心算法示例，这些示例涵盖了不同的问题类型。

示例 1: 钱币找零问题

这个例子是经典的贪心算法应用。假设你是一名售货员，需要给客户找零。有若干不同面值的硬币，目标是使用最少数量的硬币完成找零。

import java.util.Arrays;

public class ChangeMaking {

    public static void findMinCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 确保硬币是排序的
        int index = coins.length - 1;
        while (amount > 0) {
            int coinCount = amount / coins[index]; // 使用尽可能多的当前最大面额
            amount = amount % coins[index]; // 更新余额
            if (coinCount > 0) {
                System.out.println("Use " + coinCount + " of " + coins[index] + " cent coin(s)");
            }
            index--;
        }
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25, 50}; // 美国硬币面额
        int amount = 99; // 需要找的零钱
        findMinCoins(coins, amount);
    }
}

示例 2: 活动选择问题

给定多个活动，每个活动都有一个开始时间和结束时间，选择最大数量的互不重叠的活动。

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

public class ActivitySelection {

    static class Activity {
        int start, finish;

        Activity(int start, int finish) {
            this.start = start;
            this.finish = finish;
        }
    }

    public static void selectActivities(Activity[] activities) {
        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish)); // 根据结束时间排序

        int count = 1;
        int lastFinishTime = activities[0].finish;
        System.out.println("Selected activity: (" + activities[0].start + ", " + activities[0].finish + ")");

        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastFinishTime) {
                System.out.println("Selected activity: (" + activities[i].start + ", " + activities[i].finish + ")");
                lastFinishTime = activities[i].finish;
                count++;
            }
        }
        System.out.println("Total selected activities: " + count);
    }

    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 7),
            new Activity(6, 9),
            new Activity(5, 8),
            new Activity(8, 10)
        };
        selectActivities(activities);
    }
}

这些示例展示了贪心算法如何在不同的情境下被应用。贪心算法虽然简单，但不总是能得到全局最优解，它更多的是提供一种简单且有效的近似解。对于某些问题，如钱币找零问题的特定情况，贪心算法可以保证找到最优解。对于其他问题，则需要通过具体的分析来确定其有效性。