贪心

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

反悔贪心

概念

反悔贪心算法是一种优化算法，通常用于解决组合优化问题。与传统的贪心算法不同，反悔贪心算法在每一步决策之后考虑可能的反悔，以确保最终的决策是最佳的。它的目标是最小化决策的后悔或损失。

流程

  • 初始决策： 算法开始时会做出初始决策，通常基于某种贪心策略来选择一个方案。
  • 模拟反悔： 在每个决策步骤之后，算法会模拟所有可能的替代决策，计算每个替代决策的后悔值或损失。后悔值是当前决策相对于其他可能决策的性能差距。
  • 选择最小后悔： 算法会选择具有最小后悔值的替代决策作为最终决策。这意味着算法会选择对整体性能改进最大的替代决策。
  • 迭代： 反悔贪心算法会重复执行步骤 2 和步骤 3，每次迭代都会尝试改进当前的决策，直到后悔值不再减小或达到某个停止条件。

应用

反悔贪心算法的应用领域包括调度问题、路径规划、资源分配和其他组合优化问题。它通常用于处理那些难以通过传统贪心算法或动态规划方法进行求解的问题，因为它考虑了多个可能性并选择具有最小后悔的决策。

课程表 III

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：

1
2
3
4
5
6
7
8
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：

1
2
输入：courses = [[1,2]]
输出：1

示例 3：

1
2
输入：courses = [[3,2],[4,3]]
输出：0

提示:

  • 1 <= courses.length <= 10^4
  • 1 <= durationi, lastDayi <= 10^4

反悔贪心解法

按照lastDay从小到大的顺序排序数组，满足要求就添加到优先队列，增加课程，这是贪心。

如果不满足要求，就需要反悔，弹出队首（用时最长的课程），就在保持课程数量不变的前提下，尝试减少总时长，使得后续增大课程数量的概率增加。

举例：

[[5,15],[3,19],[6,7],[2,10],[5,16],[8,14],[10,11],[2,19]]

按lastDay从小到大排序

[[6,7],[2,10],[10,11],[8,14],[5,15],[5,16],[3,19],[2,19]]

下面每次遍历后，当前保留课程的duration

6
6,2
6,2
6,2
6,5,2
5,5,2
5,5,3,2
5,5,3,2,2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int scheduleCourse(int[][] courses) {
        int n = courses.length, res = 0, total = 0;
        Arrays.sort(courses, (i,j)->i[1]-j[1]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((i,j)->j-i);
        for (int i = 0; i < n; i++) {
            int duration = courses[i][0], lastDay = courses[i][1];
            // 如果能增大课程数量，就增大课程数量
            if (total + duration <= lastDay) {
                total += duration;
                pq.offer(duration);
                res += 1;
            }
            // 如果不能增大课程数量，就在保持课程数量不变的前提下，尝试减少总时长，使得后续增大课程数量的概率增加
            else if (!pq.isEmpty() && duration < pq.peek()) {
                total += duration;
                total -= pq.poll();
                pq.offer(duration);
            }
        }
        return res;
    }
}

子序列最大优雅度（2582）

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories^2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意: 数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

示例 1：

1
2
3
4
5
6
7
输入：items = [[3,2],[5,1],[10,1]], k = 2
输出：17
解释：
在这个例子中，我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。
因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。

示例 2：

1
2
3
4
5
6
7
输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出：19
解释：
在这个例子中，我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ，子序列包含 3 种不同类别 [1, 2, 3] 。 
因此，优雅度为 10 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。

示例 3：

1
2
3
4
5
6
7
输入：items = [[1,1],[2,1],[3,1]], k = 3
输出：7
解释：
在这个例子中，我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6，子序列包含 1 种不同类别 [1] 。
因此，最大优雅度为 6 + 12 = 7 。

提示：

  • 1 <= items.length == n <= 10^5
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 10^9
  • 1 <= categoryi <= n
  • 1 <= k <= n

x + y 贪心解法

res = total_profit + distinct_categories^2

items按照profit从大到小排序，取前k个，此时total_profit为最大值

枚举递增distinct_categories的所有可能（total_profit单调递减），寻找可能的更大res

考虑选第 k+1 个项目，为了选它，我们必须从前 k 个项目中移除一个项目，分类讨论：

  • 如果第 k+1 个项目和前面某个已选项目的类别相同，那么无论怎么移除都不会让 distinct_categories 变大，所以无需选择这个项目
  • 如果第 k+1 个项目和前面任何已选项目的类别都不一样，考虑移除前面已选项目中的哪一个：
    • 如果移除的项目的类别只出现一次，那么选第 k+1 个项目后，distinct_categories 一减一增，保持不变，所以不考虑这种情况
    • 如果移除的项目的类别重复出现多次，那么选第 k+1 个项目后，distinct_categories 会增加一，此时有可能会让优雅度变大，可以选择这个项目

问题抽象： res = x + y，枚举递增y的所有可能（x单调递减），寻找可能的更大res，取res的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        int n = items.length;
        long res = 0, total_profit = 0;
        Arrays.sort(items, (a, b)->b[0]-a[0]);
        Set<Integer> categories = new HashSet<>();
        Deque<Integer> duplicateProfits = new LinkedList<>();
        // res = total_profit + distinct_categories^2
        // distinct_categories = categories.size()
        for (int i = 0; i < n; i++) {
            int profit = items[i][0], category = items[i][1];
            // items按照profit从大到小排序，取前k个，此时total_profit为最大值
            if (i < k) {
                total_profit += profit;
                if (!categories.add(category)) {
                    // 把出现超过1次的category的profit加入duplicateProfits
                    duplicateProfits.push(profit);
                }
            }
            else {
                // 接下来枚举更大的distinct_categories，寻找可能的更大res
                if (duplicateProfits.size() == 0) break;
                if (categories.add(category)) {
                    total_profit += profit - duplicateProfits.poll();
                }
            }
            res = Math.max(res, total_profit + (long)categories.size() * categories.size());
        }
        return res;
    }
}