摘要

  本文主要讲解贪心法的基本思想和实现,怎么运用贪心法,着重讲解在编程竞赛中的一些典型应用。

  什么是贪心法?

  在编程竞赛中的典型应用有哪些?

  例题解析


什么是贪心法?

  贪心法本质上讲不是一种真正的算法,而是一种思想,就是解决问题的时候遵循着某种规则,不断贪心地选取当前最优策略,以达到结果最优的目的。比如硬币问题,给出1元、5元、10元、50元、100元的硬币各a、b、c、d、e个,问用这些硬币来支付A元,最少需要多少枚硬币?

  很容易想到先用面额大的钱,依次往小即可。这就是贪心法的典型应用,只顾眼前的利益最大化,从而达到总体最优的效果。

在编程竞赛中的典型应用有哪些?

  硬币问题,给出硬币的面额和个数,给出需要支付的钱数A,问至少、至多需要多少个硬币?比如HDU 3348 coins

  区间问题,给出区间的个数和各个区间的起始和终止,问不能交叉的选取,最多能选取多少个区间?比如HDu 2037 今年暑假不AC

  字典序最小问题,给出一个字符串,每次只能从头或者尾取一个字符组成另一个字符串,问字典序最小的字符串是哪个?比如POJ 3617 Best Cow Line

  点覆盖问题,给出一个点能够覆盖的范围r和点数以及每个点的位置,问最少需要多少个点使得所有的点都被覆盖? 比如POJ 3069 Saruman’s Army

  哈夫曼编码问题,给出总的木板长度,需要分割的n个木块及长度,问将这根木板分割成n段的最小代价是多少,其中切割的代价等于被切木板的长度,比如将长度为13的木板切成8和5,所花费的代价是13。比如POJ 3253 Fence Repair

例题解析

  HDU 3348 coins 问至少和至多需要多少个硬币,至少容易求,直接贪心先选取面额大的硬币即可,关键是怎么求最多需要多少硬币,有人想到还使用贪心,先选取面额小的硬币,这样是有漏洞的,优先将小的硬币选完之后,可能造成无法凑成A。

  这里采用一种反向思维的解法,要想给出的硬币最多,那么手中剩下的硬币就得最少,这样就可以按照之前的方法解题了。只不过要凑的钱数变成了sum-A,计算出的是凑完手中钱最少需要多少个硬币,再用总的硬币数减去它,就可以的到答案了。参考代码如下:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int v[5] = {1, 5, 10, 50, 100};
 6 
 7 int main()
 8 {
 9     int T;
10     int A, a[5];
11     scanf("%d", &T);
12     while(T--) {
13         scanf("%d%d%d%d%d%d", &A, &a[0], &a[1], &a[2], &a[3], &a[4]);
14         int mina = 0;
15         int p1 = A;
16         for(int i = 4; i >= 0; i--) {
17             int t = min(p1 / v[i], a[i]);
18             p1 -= t * v[i];
19             mina += t;    
20         }
21         
22         int maxa = 0;
23         int sum = a[0] + 5 * a[1] + 10 * a[2] + 50 * a[3] + 100 * a[4];
24         int p2 = sum - A;
25         for(int i = 4; i >= 0; i--) {
26             int t = min(p2 / v[i], a[i]);
27             p2 -= t * v[i];
28             maxa += t;    
29         }
30         maxa = a[0] + a[1] + a[2] + a[3] + a[4] - maxa;
31         
32         if(p1 != 0 || p2 != 0)
33             printf("-1 -1\n");
34         else
35             printf("%d %d\n", mina, maxa);
36     }
37     return 0;
38 }

  HDu 2037 今年暑假不AC 典型的区间调度问题,先将区间按照结束的早的优先级高的规则排序,然后每次选取结束时间最早的区间。用到了结构体排序,注意迭代的过程。

参考代码如下:

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 110;
 6 struct Node {
 7     int s, e;
 8 }node[maxn];
 9 bool cmp(Node a, Node b) {
10     if(a.e == b.e)
11         return a.s < b.s;
12     return a.e < b.e;
13 }
14 int main()
15 {
16     int n;
17     while(scanf("%d", &n) == 1 && n) {
18         for(int i = 0; i < n; i++) {
19             scanf("%d%d", &node[i].s, &node[i].e);
20         }        
21         sort(node, node + n, cmp);
22         
23         int ans = 0, t = 0;
24         for(int i = 0; i < n; i++) {
25             if(t <= node[i].s){
26                 ans++;
27                 t = node[i].e;
28             }
29         }
30         printf("%d\n", ans);
31     }
32     return 0;
33 }

  POJ 3617 Best Cow Line 很容易想到贪心的规则是每次从头或者尾选取较小的字符,不过需要注意的是如果两个字符相等,就需要比较后面的,换句换说就要比较一个串的正和反哪个字典序小,从而得出结论。实现较为巧妙,参考代码:

 1 /*    
 2     给出一个字符串,问每次只能从头或者尾取一个字符,组成最小字典序的字符串
 3     每次比较从左起和从右起的字符串,比较出就输出 
 4 */
 5 #include <cstdio>
 6 
 7 const int maxn = 101000;
 8 char s[maxn], rs[maxn];
 9 
10 int main() 
11 {
12     int n, cnt = 0;
13     while (scanf("%d", &n) != EOF) {
14         for (int i = 0; i < n; i++) {
15             scanf(" %c", &s[i]);
16         }
17         s[n] = '\0';
18         //puts(s); 
19         
20         int a = 0, b = n - 1;
21         while (a <= b) {
22             bool left = false;
23             //比较从左起和从右起的字符串
24             for (int i = 0; a + i <= b; i++) {
25                 if (s[a + i] < s[b - i]) {
26                     left = true;
27                     break;
28                 } else if (s[a + i] > s[b - i]) {
29                     left = false;
30                     break;
31                 }
32             }
33             
34             if (left) putchar(s[a++]);
35             else putchar(s[b--]);
36             cnt++;
37             if(cnt == 80){
38                 printf("\n");
39                 cnt = 0;
40             }
41         }
42         printf("\n");
43     }
44     return 0;
45 }

  POJ 3069 Saruman’s Army 典型的点覆盖问题,贪心的规则是保证能够覆盖最左边的点的情况下,尽量选取一个靠左点,然后跳过它能够覆盖的点,如此重复。代码如下:

 1 /*
 2     给出一个灯能够照亮的范围r,给出n个点的位置,问至少需要安装多少个灯,使得每个点都在灯的范围内
 3     使用贪心法,找到一个最左边的位置,加上r,跳过能够覆盖的所有点,找到第一个不能覆盖的点,作为灯,
 4     然后再往右走r,跳过r内的点,计数,直到走完。 
 5 */
 6 #include <cstdio>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 const int maxn = 1010;
11 
12 int a[maxn];
13 int main () 
14 {
15     int r, n;
16     while (scanf("%d%d", &r, &n) == 2 && r + n != -2) {
17         for (int i = 0; i < n; i++) {
18             scanf("%d", &a[i]);
19         }
20         sort (a, a + n);
21         
22         int i = 0, ans = 0;
23         while (i < n) {
24             int s = a[i++];
25             while (i < n && s + r >= a[i]) 
26                 i++;
27             int p = a[i - 1];
28             while (i < n && p + r >= a[i]) 
29                 i++;
30             
31             ans++;
32         }
33         printf ("%d\n", ans);
34     }
35     return 0;
36 } 

  POJ 3253 Fence Repair 该题的解法作为计算法哈夫曼编码的算法而被熟知,使用了C++ STL 中的优先队列,实现起来非常简单。优先队列自定义优先级的两种方法如下:

 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 typedef long long LL;
 5 priority_queue<int, vector<int>, greater<int> > pq;
 6 int main()
 7 {
 8     int n;
 9     while (scanf("%d", &n) != EOF) {
10         while(!pq.empty())
11             pq.pop();
12         
13         int tmp;
14         for(int i = 0; i < n; i++) {
15             scanf("%d", &tmp);
16             pq.push(tmp);
17         }
18         
19         LL ans = 0;
20         while(pq.size() > 1) {
21             int min1 = pq.top();
22             pq.pop();
23             int min2 = pq.top();
24             pq.pop();
25             
26             ans += min1 + min2;
27             pq.push(min1 + min2);
28         }    
29         printf("%lld\n", ans);
30     }
31     return 0;
32 }
 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 typedef long long ll;
 5 struct cmp {
 6     bool operator () (const int &a, const int &b) const {
 7         return a > b;
 8     }
 9 };
10 priority_queue<int, vector<int>, cmp> pq;
11 
12 int main ()
13 {
14     int n;
15     while (scanf("%d", &n) != EOF) {
16         while (!pq.empty())
17             pq.pop();
18         for (int i = 0; i < n; i++) {
19             int tmp;
20             scanf("%d", &tmp);
21             pq.push(tmp);
22         }
23         ll ans = 0;
24         while(pq.size() > 1) {
25             int min1 = pq.top();
26             pq.pop();
27             int min2 = pq.top();
28             pq.pop();
29             
30             ans += min1 + min2;
31             pq.push(min1 + min2);
32         }
33         printf("%lld\n", ans);
34     }
35     return 0;
36 }

  贪心法最大的特点就是和动态规划的相比只顾眼前的最优,熟悉动态规划的话,对贪心法会有更深层的理解,另外求解最短路中的prim算法和Dijkstra算法等都是运用了贪心法的思想。要学会并不难,关键是多动手实践。

 

  

版权声明:本文为wenzhixin原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/wenzhixin/p/9489267.html