🍕 贪心算法

【算法核心】: 只考虑局部最优解, 不考虑全局最优解。

很多情况下, 局部最优就是全局最优, 但这往往需要证明。 如果在做题中还想着去证明, 那么时间肯定会不够用的。

案例1 安排会议

给出多场会议的开始时间和结束时间, 在限定一个会议室的情况下, 如何决定会议的顺序使得可以安排的会议数量最多？

• 【贪心策略1】: 以谁最早开始会议为标准, 安排会议顺序。 这种贪心策略很容易证明是非全局最优解的, 比如一个早上6点维持到下午6点的会议
• 【贪心策略2】: 以会议持续时间最短为标准, 安排会议顺序。 这种贪心策略也是很容易证明非全局最优解的。 比如一个会议6点到12点, 一个会议12点10分到下午6点, 而有一个会议在 11:50到12:20。
• 【贪心策略3】: 以谁最早结束会议为标准, 安排会议顺序。

第三种贪心策略似乎比较靠谱, 但是我们也无法马上证明。 在考试时, 遇到这个问题, 不要去证明, 平时可以尝试, 但考试的时候不要。 考试时, 利用对数器的方案, 外加暴力枚举的方法, 验证你的贪心策略, 如果基本都成功的话, 就提交上去。 所以重点在于, 你要很熟练的写出对数器, 并且熟悉暴力枚举等方式。 不然的话, 考试时对数器都不会写, 那么这种方式也就没用了。

贪心策略的代码一般都会简单。

class Program {
    int start;
    int end;
}

int bestArrange(Program[] programs, int timePoint) {
    Arrays.sort(programs, (o1, o2) -> o1.end - o2.end ); // 按会议结束时间进行排序
    int result = 0;
    for (int i = 0; i < programs.length; i++) {
        if (timePoint <= programs[i].start) {
            result ++;
            timePoint = programs[i].end;
        }
    }
    return result;
}

案例2 最小字典序

给定一个字符串数组, 如何拼接字符串, 能够拼接出最小字典序的字符串。

【字典序大小规则】: 把单词看成 26 位进制的数, 然后在长度短的单词后补零, 最终两个单词长度一样, 然后比较大小。 比如 b 和 ba, b 补零后变成 b0, b0 < ba, 所以 b 的字典序小

【贪心策略1】: a 和 b 比较, 若 a 的字典序小, 则把 a 放前面。 这种贪心是错的, 明显的反例就是 b 和 ba 拼接, 按这种贪心排序最终会是 bba, 但实际上 bab 比 bba 字典序小。 【贪心策略2】: a 和 b 比较, 如果 a拼接b <= b拼接a, 则 a 放在前面。

贪心策略2 是正确的, 但在考试时不要想着证明。 或者说, 如果考试时自己想出了这种贪心策略, 同时无法自己找到反例时, 不要想着证明, 而是想把代码写下来, 然后去跑一下。 贪心策略的代码都是很简单的, 比如 贪心策略2 的代码如下:

String lowestString(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    Array.sort(strs, (a, b) -> (a+b) - (b+a)); // 如果 ab 字典序 < ba 字典序, 则 a 放在 b 前面
    // 排序后直接拼接起来, 最后结果就是最小字典序
    String res = "";
    for (int i = 0; i < strs.length; i++) {
        res += strs[i];
    }
    return res;
}

贪心证明

首先, 要证明我们的比较策略, 是一个有效的比较策略。 举个无效的比较策略例子: 假设一个字符串只由 "甲"、 "乙"、 "丙" 组成, 如果定义的策略是: 这就是无效的比较策略, 因为比较的结果是个环, 就像石头箭头布一样, 你没法知道谁是最强的。

如果使用无效的策略, 对数组进行排序, 那么就无法保证排序结果的唯一性。 所以不能使用无效的比较策略。

专业地讲, 要证明我们的比较策略是有效的, 就需要证明我们的比较策略具有 "传递性"。

【证明比较策略具有传递性】:

• 要证明比较策略有传递性, 需要证明的是:
  • 如果 $ab$ $\le$ $ba$
  • 且 $bc$ $\le$ $cb$
  • 则 $ac$ $\le$ $ca$
• 我们把这些单词看成是 $k$ 进制, $k=26$, 那么 $ab$ 就可以写成 $a\ast k^{(}b\mathrm{长}\mathrm{度})+b$, 我们用 $a\ast m(b)$ 来表示 $a\ast k^{(}b\mathrm{长}\mathrm{度})+b$
  • 举个例子, 比如数字 12345, 可以看成是 $123\ast {10}^2+45$, 其中的 ${10}^2$ 的 $2$ 表示 $45$ 的长度。
• 故证明的内容可以改写成:
  • 如果 $a\ast m(b)+b$ $\le$ $b\ast m(a)+a$, ①
  • 且 $b\ast m(c)+c$ $\le$ $c\ast m(b)+b$, ②
  • 则 $a\ast m(c)+c$ $\le$ $c\ast m(a)+a$ ③
• 对第一个不等式 ① 两边同时减去 $b$ 再乘 $c$, 得到:
  • $a\ast m(b)\ast c$ $\le$ $b\ast m(a)\ast c+a\ast c-b\ast c$, ④
• 对第二个不等式 ② 两边同时减去 $b$ 再乘 $a$, 得到:
  • $b\ast m(c)\ast a+c\ast a-b\ast a$ $\le$ $c\ast m(b)\ast a$, ⑤
• 可以发现, 不等式 ④ 的左侧等于不等式 ⑤ 的右侧, 所以得到:
  • $b\ast m(c)\ast a+c\ast a-b\ast a$ $\le$ $b\ast m(a)\ast c+a\ast c-b\ast c$, ⑥
• 化简不等式 ⑥, 首先两边同时减去 $c\ast a$, 得到
  • $b\ast m(c)\ast a-b\ast a$ $\le$ $b\ast m(a)\ast c-b\ast c$, ⑦
• 然后两边同时除以 $b$, 得到:
  • $m(c)\ast a-a$ $\le$ $m(a)\ast c-c$, ⑧
• 然后将两边的 $-a$ 和 $-c$ 互换一下变成 $+c$ 和 $+a$, 得到:
  • $m(c)\ast a+c$ $\le$ $m(a)\ast c+a$, ⑨
• 最终得到的不等式 ⑨, 就是前面的不等式 ③, 故成功证明我们的比较策略是有传递性的

证明了比较策略是有效的后, 只证明了: 不管使用什么排序算法, 都能保证最终的结果是唯一的。

【证明通过上面的比较策略得出的字典序是最小的】: - 我们使用反证法证明: 假设一个字符串数组, 使用上面的比较策略后拼接成的字符串是 "……a……b……" 不是字典序最小的, 即存在 a b 两个字符交换后的字符串 "……b……a……" 的字典序比 "……a……b……" 字典序更小。

• 假设一个字符串数组, 使用上面的比较策略后拼接成的字符串是 "……a……b……"
  • 我们需要证明的是交换 a 和 b 两个字符后的字符串 "……b……a……" 字典序更大。
• 情况1, ab 是拼接在一起的, 即 "……ab……" 和 "……ba……"
  • 因为 ab 是我们使用比较策略后拼接的结果, 所以一定满足 ab ≤ ba
• 情况2, a 和 b 不是拼接在一起的, ab 之间有若干个字符 $m_1$, $m_2$, 即 "……a$m_1$$m_2$b……", "……b $m_1$$m_2$ a……"
• 如果我们将 a 往后移动, 即 a$m_1$ 交换成 $m_1$a, 我们能保证 $m_1$a 的字典序会变大
• 同理 b 往前移动, 我们也能保证 b$m_2$ 比 $m_2$b 更大,
• 以此类推, 通过数学归纳法, 最终就能够证明, 对于拼接后的字符串, 不管交换哪两个字符, 都会让字典序变大。

案例3 哈夫曼编码

群人想整分整块金条, 怎么分最省铜板? 例如,给定数组 [10,20,30], 代表一共三个人, 整块金条长度为10+20+30=60。 金条要分成 10,20,30 分别给三个人。 如果先把长度 60 的金条分成 10 和 50, 花费 60; 再把长度 50 的金条分成 20 和 30, 花费 50; 一共花费 110 铜板。 但是如果先把长度 60 的金条分成 30 和 30, 花费 60; 再把长度 30 金条分成 10 和 20 花费 30。 一共花费 90 铜板。

输入一个数组, 返回分割的最小代价

上面题意, 就是在说, 一个数字 60, 每次只能切割成两部分, 并且切割的代价是 60。 现在要将 60 切割成 10,20,30, 请问如何切割代价最小。 答案就是 先将 60 切成 30 和 30, 此时代价 60, 再将 30 切割成 10 和 20, 此时代价 30, 总代价 90。

抽象一下题意, 就是哈夫曼编码问题: 给定一个数组, 将他们构成一棵树, 要让最终树的数字之和最小。 比如数组 [10, 20, 30], 如果先将 20 和 30 合成一颗子树, 头节点就是 50, 然后再利用 50 和 10 构成一棵完整的树, 头节点就是 60。 但如果先将 10 和 20 构成一颗子树, 然后再将这棵子树和 30 构成完整的一棵树, 这棵树的数字之和会比前一种方法小。

    60          60
  /   \       /   \
 10   50     30   30
     /  \        /  \
    20  30      20  10

【哈夫曼编码步骤】:

• 每次从数组中选取出最小的两个数, 将他们构成一棵子树, 子树头节点的值为两个数之和
• 构造完后, 再把这棵子树的头节点值放到数组中, 然后重复前一步
• 直到最终构成一棵完整的树, 即数组中只剩下一个数, 这个树就是根节点的值。

int lessMoney(int[] arr) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < arr.length; i++) {
        pq.add(arr[i]);
    }
    int sum = 0;
    int cur = 0;
    while (pq.size() > 1) {
        cur = pq.poll() + pq.poll();
        sum += cur; // 去除两个最小的数;   或者说切割的代价;    反正就是合成的子树的头节点的值就是了。
        pq.add(cur);
    }
    return
}

案例4 项目利润

【输入】:

• 正数数组costs
  • costs[i]表示i号项目的花费
• 正数数组profits
  • profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
• 正数k
  • k表示你只能事行的最多做k个项目
• 正数m
  • m表示你初始的资金

【说明】: 你每做完一个项目, 马上获得的收益, 可以支持你去做下一个项目

【输出】: 你最后获得的最大钱数。

class Node { // 表示一个项目
    int c;  // 项目要求资金
    int p; // 项目利润
}
int findMaximizedCapital(int k, int w, int[] Profits, int[] Capital) {
    PriorityQueue<Node> minCostQ = new PriorityQueue<>( (a, b) -> a.c-b.c ); // 小根堆, 根据资金从小到大排序排序。 每次从中取出资金足够的项目, 拿到 大根堆中
    PriorityQueue<Node> maxProfitQ = new PriorityQueue<>( (a,b) -> b.p-a.p ); // 大根堆, 根据利润从大到小排序。 只存放当前资金足以去做的项目
    for (int i = 0; i < Profits.length; i++) {
        minCostQ.add(new Node(Profits[i], Capital[i]));
    }
    for (int i = 0; i < k; i++) { // 最多只允许执行 k 个项目
        while (!minCostQ.isEmpty() && minCostQ.peek().c <= w) { // 取出所有能做的(资金足够)的项目
            maxProfitQ.add(minCostQ.poll()); // 将资金足够的项目加到大跟堆中
        }
        if (maxProfitQ.isEmpty()) {
            return w; // 大根堆为空, 所以不再有项目能够做了, 资金无法再增长
        }
        w += maxProfitQ.poll().p; // 每次制作利润最大的项目, 做完后, 资金都会增加。
    }
}