第10课 贪心2

❝真正厉害的人，往往都比较“贪心”.❞

「所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。」 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

示例

在一个山洞里发现了5个宝石

宝石编号	1	2	3	4	5
宝石体积	2	4	3	9	7

现在你有个背包, 容量是 10.

状态: 当前背包里已经放了多少宝石, 背包还剩多少体积 策略: 选择宝石的方法

• 怎么选装下的宝石个数最多呢?

这个比较简单, 直接选体积最小的就可以贪心的装了, 没有反例. 无论当前什么状态, 选择体积最小的都是最优方法.

• 怎么选装下的体积和最大呢???

贪心啊, 所以选体积最大的 9 然后, 然后没得选了. 贪心啊, 选体积最小的, 这样剩下空间大可以装更多的. 选 2, 然后选 3, 4. 还是总体积还是 9. 可如果选 3 和 7, 能得到体积 10.

贪心策略应该是装满, 可是我们不知道怎么才能装满, 不是先装最小的, 也不是先装最大的. 这个时候可以暴力枚举, 当然最好的方式是后面会学到的动态规划.

贪心只考虑当前状态, 所以实现起来比较简单, 但证明一道题目符合贪心比较难.

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解.

贪心算法适用的问题

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

贪心算法的基本思路

• 建立数学模型来描述问题。
• 把求解的问题分成若干个子问题。
• 对每一子问题求解，得到子问题的局部最优解。
• 把子问题的解局部最优解合成原来解问题的一个解。

贪心算法的实现框架

    从问题的某一初始解出发；
    while （能朝给定总目标前进一步）
    {
          利用可行的决策，求出可行解的一个解元素；
    }
    由所有解元素组合成问题的一个可行解；

P1223 排队接水

题目描述

有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 ，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。

输入格式

第一行为一个整数 n。

第二行 n 个整数，第 i 个整数 表示第 i 个人的等待时间 。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

输入输出样例

• 输入 #1复制

10
56 12 1 99 1000 234 33 55 99 812

• 输出 #1复制

3 2 7 8 1 4 9 6 10 5
291.90

说明/提示

n≤1000，t_i≤10⁶

不保证t_i不重复。

分析

ai 和 bi 且 ai < bi

那么针对这两个元素：就有两种排列情况：

1. ai排在bi前面那么有总时间：t1 = ai + ai + bi.
2. bi排在ai前面那么有总时间：t2 = bi + bi + ai.

1 和 2的时间差为 t2 – t1 = (bi + bi + ai) – (ai + ai + bi)

得出 t2 – t1 = bi – ai;

因为 bi 比 ai 大, 所以 t2 也比 t1 大.

于是得出结论：当 ai 在 bi 前面时，时间为最小值。

于是反推回总体，两两相较，那么越小的应该越排在前面，以至于总时间越小

参考代码

#include<bits/stdc++.h>
using namespace std;

struct water {
    int idx;
 int time;
};
water w[1008];
double t;
int n;


bool compare(water w1 ,water w2) {
    return w1.time < w2.time;
}

int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&w[i].time);
        w[i].idx=i;
    }

    sort(w+1, w+n+1, compare);
    for(int i=1; i<=n; i++) {
     printf("%d ", w[i].idx);
     t+=w[i].time * (n- i);
 }

    printf("\n");
    printf("%.2f",t/n);

    return 0;
}

上面的题目的贪心策略还算好找, 下面这道题目就有点难了.

P1803凌乱的yyy / 线段覆盖

题目背景

快 noip 了，yyy 很紧张！

题目描述

现在各大 oj 上有 n 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 2 个及以上的比赛。

输入格式

第一行是一个整数 n ，接下来 n 行每行是 2 个整数 $a_{i},b_{i} ( a_{i}<b_{i})$ ，表示比赛开始、结束的时间。<=”” p=””>

输出格式

一个整数最多参加的比赛数目。

输入输出样例

• 输入

3
0 2
2 4
1 3

• 输出

2

说明/提示

对于 20% 的数据，n≤10

对于 50% 的数据，n≤10³ 。

对于 70% 的数据，n≤10⁵  。

对于 100% 的数据， n≤10⁶ ，0≤a_i<b_i≤10⁶ 。

分析

这道题目抽象成下面的问题:

在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。

最左边的线段放什么最好？

显然放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少

其他线段放置按右端点排序，贪心放置线段，即能放就放

参考代码

#include<bits/stdc++.h>
using namespace std;

int n;
int cnt;

struct line{
    int start;
    int end;
};

line l[1000008];
bool compare(line l1, line l2){
 return l1.end < l2.end;
}

int main()
{
 int i, tend;

    scanf("%d",&n);
    for(i=0; i<n; i++) {
     scanf("%d %d", &l[i].start, &l[i].end);
 }
 sort(l, l+n, compare);

 tend = 0;
 for(i=0; i<n; i++) {
  if(l[i].start>=tend) {
   cnt++;
   tend=l[i].end;
  }
    }

 printf("%d", cnt);

 return 0;
}

复杂点的题目是贪心 + 其他算法的综合. 比如下面这道题目.

P1090 合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 = 3+12=15 。可以证明 15 为最小的体力耗费值。

输入格式

共两行。

第一行是一个整数  ，表示果子的种类数。

第二行包含 n 个整数，用空格分隔，第 i 个整数  是第 i 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于  。

输入输出样例

• 输入

3
1 2 9

• 输出

15

说明/提示

对于30％的数据，保证有 n≤1000：

对于50％的数据，保证有 n≤5000；

对于全部的数据，保证有 n≤10000。

分析

贪心策略: 先找到两个最小的，进行合并，然后再放回去. 如果每次合并完, 调用sort 进行快排, 找到两个最小的, 会超时. 用堆排序(优先队列)比较好, 其实修改插入排序也能过.

参考代码

#include <bits/stdc++.h>
using namespace std;

int n;
int a[10008];
int total, tmp;

void change(int start)
{
 int i;
 int  tmp = a[start];
 for(i = start+1; i < n; i++) {
  if(a[i] < tmp) {
   a[i-1] = a[i];
  } else
   break;
 }

 a[i-1] = tmp;
}

int main()
{
 scanf("%d", &n);
 for(int i = 0; i < n; i++) {
  scanf("%d", &a[i]);
 }

 sort(a, a+n);

 for(int i = 0; i < n - 1; i++) {
  a[i + 1] = a[i] + a[i + 1];
  total += a[i + 1];
  change(i + 1);
  //sort(a + i + 1, a+n);  //50分
 }

 printf("%d", total);

 return 0;
}

总结

对于贪心题目, 贪心策略可以大胆假设, 小心求证. 证明不出来, 时间充裕的情况, 可以试着找找极端情况下的反例. 时间有限的情况下, 默认自己是对的. 通常贪心的做法也能得点分, 甚至可以多种贪心策略下求出几个解后, 再选最优解.