贪心算法:分阶段的工作,在每个阶段做出当前最好的选择,从而希望得到结果是最好或最优的算法。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。
任务调度问题(简单)
这是一个经典简单的贪心问题,只是题目有点长需要认真读。解决这个问题,重点要想好贪心的策略:
阶段性:每个时间表选择哪一个任务。
贪心策略:根据“误时惩罚”对任务进行排序,优先排惩罚大的任务,如果这个时间点已经被占了,依次向前找,判断任务是否能安排?
1 #include <stdio.h>
2 #include <stdlib.h>
3 typedef struct{
4 int time;
5 int weight;
6 }obj,*object;
7
8 object objs;
9 int num = 0;//任务数
10 int totle = 0;
11 int order[500];//任务序列
12
13 //冒泡排序
14 void bubble(){
15 obj tmp;
16 for(int i=0;i<num-1;i++){
17 for(int j=0;j<num-i-1;j++)
18 if(objs[j].weight>objs[j+1].weight){
19 tmp = objs[j];
20 objs[j] = objs[j+1];
21 objs[j+1] = tmp;
22 }
23 }
24 }
25
26 void range(){
27 for(int i=num-1;i>=0;i--){
28 if(order[objs[i].time]==0){
29 order[objs[i].time] = 1;
30 }else{
31 int j = objs[i].time;
32 bool change = false;
33 for(;j>=1;j--)
34 if(order[j]==0){
35 change = true;
36 order[j] = 1;
37 break;
38 }
39 if(!change)
40 totle+=objs[i].weight;
41 }
42 }
43 }
44
45 int main()
46 {
47 scanf("%d",&num);
48 //初始化结构体对象
49 objs = (object)malloc(num*sizeof(obj));
50 for(int i=0;i<num;i++)
51 scanf("%d",&objs[i].time);
52 for(int i=0;i<num;i++)
53 scanf("%d",&objs[i].weight);
54 bubble();
55 range();
56 printf("%d",totle);
57 return 0;
58 }
区间覆盖(开始没思路)
感觉这个贪心的策略比较难想,不过接触一次以后就会有思路啦。
阶段性:每个区间选择那两个点
贪心策略:
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 using namespace std;
6
7 struct node
8 {
9 int x,y;
10 }a[10005];
11 bool used[10005];
12 int n;
13 int ans;
14
15 int cmp(node a,node b)
16 {
17 return a.y<b.y;
18 }
19
20 int main()
21 {
22 cin>>n;
23 for(int i=1;i<=n;i++)
24 cin>>a[i].x>>a[i].y;
25 sort(a+1,a+n+1,cmp);
26 for(int i=1;i<=n;i++)
27 {
28 int k=0;
29 for(int j=a[i].x;j<=a[i].y;j++)
30 if(used[j])
31 k++;
32 for(int j=a[i].y;j>=a[i].x&&k<2;j--)
33 if(!used[j])
34 {
35 used[j]=1;
36 k++;
37 ans++;
38 }
39 }
40 cout<<ans<<endl;
41 return 0;
42 }
最小差距 (题有点坑,提交了好多次)
贪心策略:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int a[15];
4 int n;
5 int abs(int x){ return (x<0?-x:x); }
6 int simple(){
7 if (a[1]==0) swap(a[1],a[2]);
8 int s1=0,s2=0;
9 for (int i=1;i<=n/2+1;i++) s1=s1*10+a[i];
10 for (int i=n;i>=n/2+2;i--) s2=s2*10+a[i];
11 return abs(s1-s2);
12 }
13 int doubles(){
14 int book[15];
15 int s1,s2;
16 int ans=(1<<31)-1;
17 for (int i=2;i<=n;i++)
18 if (a[i-1]){
19 s1=a[i],s2=a[i-1];
20 memset(book,0,sizeof(book));
21 book[i]=book[i-1]=1;
22 int l=1,r=n;
23 for (int j=1;j<=(n-2)/2;j++){
24 while (book[l]) l++;
25 while (book[r]) r--;
26 book[l]=book[r]=1;
27 s1=s1*10+a[l];s2=s2*10+a[r];
28 }
29 ans=min(ans,abs(s1-s2));
30 }
31 return ans;
32 }
33 int main(){
34 int t;
35 cin>>t;
36 while (t--){
37 scanf("%d",&n);
38 for (int i=1;i<=n;i++) scanf("%d",&a[i]);
39 sort(a+1,a+1+n);
40 if (n==2) {
41 printf("%d\n",a[2]-a[1]);
42 continue;
43 }
44 if (n%2==1)
45 printf("%d\n",simple());
46 else
47 printf("%d\n",doubles());
48 }
49 }
50
51 /*
52 N为奇数 N为偶数 N=2
53 对于第一种情况,不难想到这样的贪心策略:将最小的非0数字作为x的最高位,然后依次从左往右取k位加入x,从右往左取k位作为y,x-y的绝对值即为答案。
54 对于第二种情况,稍微复杂些:枚举非零数字a[i]作为x的最高位,a[i+1]作为y的最高位,从右往左取k-1位加入x,从左往右取k-1位加入y,打擂台更新答案。
55 对于第三种情况,特判输出。
56 */
最近做了一些贪心算法的题,感觉贪心算法主要是根据问题的要求想出贪心策略,上面提到了没有涉及到什么数据结构和高精度的问题。所以用到最多的就是排序。