04-贪心

贪心

能采用贪心算法求最优解的问题，一般具有的重要性质为：最优子结构性质与贪心选择性质。

贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到，这是贪心法和动态规划法的主要区别。

贪心法的求解过程：

1. 把求解的问题分成若干个子问题
2. 对每个子问题求解，得到子问题的局部最优解
3. 把子问题的解局部最优解合成原来解问题的一个解

虽然贪心法每一步都能获得局部最优解，但由此产生的全局解有时不一定是最优的。

活动安排问题

设有n个活动的集合，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且。如果选择了活动i，则它在时间区间内占用资源。若区间与区间不相交，则称活动i与活动j是相容的。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

活动安排问题的贪心选择策略：每次选择最早结束的

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.ArrayList;
import java.util.List;

@Data
@AllArgsConstructor
class Activity {
    int id;
    int start;
    int end;
    boolean selected;
}

public class Greedy {
    // 贪心法解决活动安排问题，返回最多安排的活动数
    public static int greedySelection(List<Activity> activities) {
        // 以活动最早结束时间作为贪心选择策略
        activities.sort(((o1, o2) -> {
            if (o1.start == o2.start)
                // 如果开始时间相同，则按结束时间从早到晚排序
                return o1.end - o2.end;
            // 先按活动开始时间从早到晚排序
            return o1.start - o2.start;
        }));
        // 初始选择安排活动0
        activities.get(0).selected = true;
        // 最近一次安排的活动序号
        int prev = 0;
        // 一共安排了几个活动
        int count = 1;
        for (int i = 1; i < activities.size(); i++) {
            // 如果第i个活动与最近一次安排的活动相容，则安排第i个活动
            if (activities.get(i).start >= activities.get(prev).end) {
                activities.get(i).selected = true;
                prev = i;
                count++;
            } else { // 不相容
                activities.get(i).selected = false;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List<Activity> activities = new ArrayList<>();
        activities.add(new Activity(4, 0, 2, false));
        activities.add(new Activity(2, 1, 3, false));
        activities.add(new Activity(1, 3, 6, false));
        activities.add(new Activity(3, 5, 9, false));
        activities.add(new Activity(5, 7, 9, false));
        activities.add(new Activity(7, 9, 11, false));
        activities.add(new Activity(6, 9, 12, false));
        activities.add(new Activity(8, 12, 14, false));
        System.out.println(greedySelection(activities));
        for (Activity activity : activities) {
            if (activity.selected)
                System.out.println(activity);
        }
    }
}