算法初步——贪心

简单贪心

PAT B1020 月饼

题意：现有月饼需求量为D，已知 n 种月饼的库存量和总售价，问如何销售这些月饼，使得可以获得的收益最大。求最大收益

思路：总是选择单价最高的月饼出售，可以获得最大利润

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 struct mooncake {    // 月饼 
 8     double store;    // 库存 
 9     double sell;    // 总售价 
10     double price;    // 单价 
11 } cake[1010];
12 bool cmp(mooncake a, mooncake b) {    // 按单价从大到小排列 
13     return a.price > b.price;
14 }
15 
16 int main() {
17     int n, d;    // n 月饼总类数，d 市场最大需求量
18     double sum = 0.0f;    // sum 最大收益 
19     scanf("%d %d", &n, &d);
20     for(int i=0; i<n; ++i) {    // 输入库存量 
21         scanf("%lf", &cake[i].store);
22     } 
23     for(int i=0; i<n; ++i) {    // 输入总售价 
24         scanf("%lf", &cake[i].sell);
25     } 
26     for(int i=0; i<n; ++i) {    // 计算单价 
27         cake[i].price = cake[i].sell/cake[i].store;
28     } 
29     sort(cake, cake+n, cmp);    // 按照单价排序
30     for(int i=0; i<n; ++i) {
31         if(cake[i].store <= d) {    // 需求量高于库存 
32             sum += cake[i].sell; 
33             d -= cake[i].store;        // 全部卖出 
34         } else if(cake[i].store > d) {    // 需求量低于库存 
35             sum += cake[i].sell/(cake[i].store/d);    // 部分卖出 
36             break;
37         }
38     } 
39     printf("%.2f
", sum);        // 输出2位小数 
40     
41     return 0;
42 }

PAT B1023 组个最小数

题意：给定数字 0~9 各若干个。可以任意顺序排序这列数字，但必须全部使用。请编写程序输出能够组成最小的数

思路：第一个数从 1~9 选取，接下来的数从 0~9 选取，依次输出

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 int main() {
 8     int count[10] = {0};    // 储存 0~9 的个数 
 9     for(int i=0; i<10; ++i) {
10         scanf("%d", &count[i]);
11     } 
12     
13     // 从 1~9 选数 
14     for(int i=1; i<10; ++i) {
15         if(count[i] > 0) {        // 找到存在的最小数 
16             printf("%d", i);    // 打印最小数 
17             count[i]--;            // 个数 -1 
18             break;
19         } 
20     }
21     // 0~9 依次输出
22     for(int i=0; i<10; ++i) {
23         for(int j=0; j<count[i]; ++j) {
24             printf("%d", i);
25         }
26     } 
27 
28     return 0;
29 }

区间贪心

　　区间不相交问题：给出 N 个开区间（x,y），从中选择尽可能多的开区间，使得这些开区间两两不相交。例如对开区间 (1,3)、(2,4)、(3,5)、(6,7) 来说，可以选取最多三个区间 (1,3)、(3,5)、(6,7) ，它们互相没有交集。

题意：输入 n 个开区间，从中选择尽可能多的开区间，使得这些开区间两两不相交。并输出开区间数

思路：

当开区间 I1 被开区间 I2 包含，选择 I1

将所有开区间按左端点 x 从大到小排序，如果去除掉么区间包含的情况，那么一定有 y1>y2>...>yn，此时总是先选取左端点最大的区间

 1 #include <cstdio>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const int maxn = 110;
 8 struct Inteval {
 9     int x, y;
10 } I[maxn];
11 bool cmp(Inteval a, Inteval b) {
12     if(a.x != b.x)    return a.x > b.x;    // 先按左端点从大到小排序 
13     else return a.y < b.y;                // 左端点相同的情况下按右端点从小到大排序 
14 } 
15 
16 int main() {
17     int n;
18     while(scanf("%d", &n), n!=0) {
19         for(int i=0; i<n; ++i) {
20             scanf("%d%d", &I[i].x, &I[i].y);
21         }
22         
23         sort(I, I+n, cmp);        // 区间排序
24         // ans 记录开区间数， lastX 记录上个区间的左端点 
25         int ans=1, lastX=I[0].x;
26         // 总是选取满足条件的左端点最大的区间 
27         for(int i=1; i<n; ++i) {
28             if(I[i].y <= lastX) {    // 若该端点的右端点在 lastX 左边 
29                 lastX = I[i].x;        // 以 I[i] 作为新选中的区间 
30                 ans++;                 // 不相加区间数 +1 
31             }
32         }
33         
34         printf("%d
", ans);
35     } 
36 
37     return 0;
38 }

值得注意的是，总是先选择右端点最小的区间的策略也是可行的
与这个问题类似的是区间选点问题：给出 N 个闭区间 [x,y] ，求最少需要确定多少个点，才能使每个中都至少存在一个点
- 对左端点最大的区间 I1 来说，只要取左端点即可
- 只需要把区间不相交问题代码中的 I[i].y <= lastX 改为 I[i].y < lastX 即可

　　总的来说，贪心是用来解决一类最优化问题，并希望由局部最优策略来推得全局最优结果的算法思想。