算法笔记 贪心

贪心是求解一类最优化问题的方法，通过局部最优，使得全局最优。

一、简单贪心

【PAT B1020】月饼

思路：

  • 采用总是选择单价最高的月饼出售的策略
  • 对每种月饼，都根据其库存量和总售价来计算出该种月饼的单价
  • 将所有月饼按单价从高到低排序
  • 从单价高的月饼开始枚举。若库存不足以满足，则全部卖出，需求减去库存值，收益加上总售价；若库存足以满足，则只提供需求量大小的月饼，收益加上需求乘以单价，需求设为 0

注意点：

  • 月饼的库存量和总售价设为浮点数，方便之后计算
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
32
33
34
#include <stdio.h>
#include <algorithm>
using namespace std;

struct mooncake{
    double store;  //库存量
    double sell;  //总售价
    double price;  //单价
}cake[1010];
bool cmp(mooncake a, mooncake b){
    return a.price > b.price;
}
int main(){
    int n;
    double d;
    scanf("%d %lf", &n, &d);
    int i;
    for (i = 0; i < n; i++)    scanf("%lf", &cake[i].store);
    for (i = 0; i < n; i++)    scanf("%lf", &cake[i].sell);
    for (i = 0; i < n; i++)    cake[i].price = cake[i].sell / cake[i].store;
    sort(cake, cake + n, cmp);  //按单价排序
    double ans = 0;  //收益
    for (i = 0; i < n; i++){
        if (cake[i].store <= d){
            d -= cake[i].store;
            ans += cake[i].sell;
        }
        else{
            ans += cake[i].price * d;
            d = 0;
        }
    }
    printf("%.2f", ans);
}

​

【PAT B1023】组个最小数

思路：

  • 先从 1~9 中找到不为 0 的最小数，输出
  • 将剩余数字从小到大依次输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

int main(){
    int i;
    int a[10];
    for (i = 0; i < 10; i++)    scanf("%d", &a[i]);
    for (i = 1; i < 10; i++)
        if (a[i] > 0){
            printf("%d", i);
            a[i]--;
            break;
        }
    for (i = 0; i < 10; i++)
        while (a[i] > 0){
            printf("%d", i);
            a[i]--;
        }
}

​

二、区间贪心

区间不相交问题

给出 N 个开区间 (x, y) ，从中选择尽可能多的开区间，使得这些开区间两两没有交集。

例如：对于开区间 (1, 3)、(2, 4)、(3, 5)、(6, 7) 来说，可以选出最多三个区间 (1, 3)、(3, 5)、(6, 7) ，它们之间互相没有交集。

首先考虑最简单的情况，如果开区间 I1 被开区间 I2 包含，如左图所示，显然选择更小区间是更好的选择。（因为选择了小区间，就会有更多空间可以容纳其它区间）在这种情况下，选择左端点最大或右端点最小的区间。

如右图所示，把所有开区间按左端点 x 从大到小排列，不考虑区间包含，那么一定有 y1 > y2 > ··· >yn 成立（否则 x2 > x1 且 y2 > y1，发生区间包含）。观察发现 I1 的右边一定有一段不与其它区间重叠（因为 y1 > y2），在考虑问题时将此段忽略，那么 I1 的左边剩余部分就会被 I2 包含，因此应当选择 I1 。对这种情况，总是选择左端点最大的区间。

综上，在两种情况下，都可以选择左端点更大的区间，当左端点大小相同时，选择右端点更小的区间。

解题思路：

  • 先将区间按左端点从大到小排序，相同则按右端点从小到大排序
  • 按顺序依次选择结点，所选结点右侧不能超过已选结点的左侧，用变量标记已选结点的左端点
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
32
33
34
35
36
37
38
/*
在将区间按左端点从大到小排序，相同则按右端点排序后
*/


#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn = 110;
struct Inteval{
    int x;
    int y;
} I[maxn];
//排序比较函数，先按左端点从大到小排序，相同则按右端点从小到大排序
bool cmp(struct Inteval a, struct Inteval b){
    if (a.x != b.x)    return a.x > b.x;
    else return a.y < b.y;
}
int main(){
    int i;
    int n;
    scanf("%d", &n);
    for (i = 0; i < n; i++)    scanf("%d %d", &I[i].x, &I[i].y);
    sort( I, I + n, cmp);  //对区间进行排序
    for (i = 0; i < n; i++){
        printf("%d %d\n", I[i].x, I[i].y);
    }
    int num = 1; //不相交区间个数，首先选中了I[0]
    int lastx = I[0].x;  //记录上一个被选中区间的左端点
    for (i = 1; i < n; i++){
        if (I[i].y <= lastx){  //如果该区间的右端点在 lastx 的左边
            lastx = I[i].x;
            num++;
        }
    }
    printf("%d\n", num);
}

区间选点问题

开区间

给出 N 个开区间 (x, y) ，求最少需要确定多少个点，才能使每个开区间都至少存在一个点。

例如：对于开区间 (1, 3)、(2, 4)、(3, 5)、(6, 7) 来说，至少需要 3 个点。

此问题与区间不相交问题完全相同。

​

闭区间

给出 N 个闭区间 [x, y] ，求最少需要确定多少个点，才能使每个闭区间都至少存在一个点。

例如：对于闭区间 [1, 3]、[2, 4]、[3, 5]、[6, 7] 来说，至少需要 2 个点。

此问题与区间不相交问题类似，但不完全相同。

解题代码需要将 I[i].y <= lastx 修改为 I[i].y < lastx ，因为在闭区间的情况下，如果两个区间相接，只需要在邻接处落点就可以同时覆盖两个区间。

​

参考

  • 算法笔记