贪心算法笔记

贪心算法

根据b站视频整理的
视频地点：https://www.bilibili.com/video/BV1f84y1i7mv/?spm_id_from=333.337.search-card.all.click&vd_source=6335ddc7b30e1f4510569db5f2506f20
原理拆解：

1.根据当前情况，做出一步最佳选择；
2.做出选择，永不改变、悔恨（区别回溯算法会悔恨）
3.云云循环，用局部最优解，渐渐得到整体最优解。
算法1（入门）：

海盗船掠夺商船，每件宝物的价值相同，但重量差异（8，20，5，45，47，90，890，60），海盗船最大蒙受重量为500，问：最大装几件宝物？

1. #include <stdio.h>
2. #include <algorithm>
3. int main(){
4.         int data={8，20，5，45，47，90，890，60};
5.         int max=500;
6.         int count=sizeof(data)/sizeof(data[0]);  //计算数组长度
7.         std::sort(data,data+count);  //排序接口
8.         int n=0;//记录宝物个数
9.         int temp=0;//已装宝物重量
10.         for(int i=0;i<count;i++){
11.                 temp+=data[i];
12.                 if(temp>max)
13.                         break;
14.                 n++;
15.         }
16.         cout<<"最大宝物个数："<<n;
17.         return 0;
18. }

复制代码

算法2（初级）：

一个很长的花坛，一部分地已经种植了花，另一部分却没有。花不能种植在相邻的地块上否则它们会争夺水源，两者都会死去。
给你一个整数数组表示花坛由多少0和1组成0表示没种植花，1表示种植了花。
给定一个数n能不能种下n朵花?

1. #include<stdio.h>
3. bool canZ(int *data, int n){
4.         int i;
5.         int datasize=sizeof(data)/sizeof(data[0]);
6.         if (n==0) return true;
7.         int count=0;
8.         while(i<datasize){
9.                 if(data[i]==1) i+=2;
10.                 else if(i>0&data[i-1]==1) i+=1;// 左边有花，走一步
11.                 else if(i+1<datasize&data[i+1]==1) i+=3; // 右边有花，走三步
12.                 esle return true;
13.         }
14.         return false;
15. }
17. int main(){
18.         int *data={1,0,0,0,1,0,1,0,0,0,0,0,1}
19.         if(canZ(data,4)) cout<<"OK";
20.         else cout<<"NO";
21.         return 0;
22. }

复制代码

算法3（中级）：

给定一个整数数组，表示在同一行的行星。
每一个元素，其绝对值表示行星的大小正负表示行星的移动方向正表示向右移动，负表示向左移动每一颗行星以相同的速度移动。
碰撞规则：
1、两个行星碰撞，较小的行星会爆炸。
2、如果大小相同，则两颗都会爆炸。
3、两颗移动方向相同的行星，永远不会发生碰撞。

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<math.h>
5. int *collision(int *data,int datasize,int *retsize){
6.         int n=0;//记录爆炸次数
7.         while(1){
8.                 int pre=0;
9.                 int next=0;
10.                 while(next<datasize){
11.                         if(data[pre]*data[next]<0){ // 运动方向相反
12.                                 if(data[pre]<0){ // 左边向左，右边想右，不会碰撞
13.                                         pre=next;
14.                                         next++;
15.                                         continue;
16.                                 }
17.                         }                               
18.                         else if(abs(data[pre]) < abs(data[next])){ // 发生碰撞了，小的爆炸
19.                                 data[next]=0;
20.                                 n++;
21.                         }
22.                         else if(abs(data[pre]) > abs(data[next])){ // 发生碰撞了，小的爆炸
23.                                 data[pre]=0;
24.                                 n++;
25.                         }
26.                         else { // 发生碰撞了，相同大小的爆炸
27.                                 data[pre]=0;
28.                                 data[next]=0;
29.                                 n+=2;
30.                         }
31.                         break;       
32.                 }
33.                 if(data[pre]==0){ // 左边已经碰撞了
34.                         pre=next;
35.                         next++;
36.                 }
37.                 else if(data[next]==0){ // 右边已经碰撞了
38.                         next++;
39.                 }
40.                 else{ // 方向相同
41.                         pre=next;
42.                         next++;
43.                 }
44.                 if(next>=datasize)
45.                         break;
46.         }
47.         int *retsize=datasize-n;
48.         int *retArray=(int *)malloc(*retsize * sizeof(int)); // 分配一个存储数组
49.         for(int i=0,k=0;i<size;i++){
50.                 if(data[i])
51.                         retArray[k++]=data[i];
52.         }
53. }
55. int main(){
56.         int data[]={10,2,-5};
57.         int size;
58.         int *ret=collision(data,3,&size);
59.         for(int i=0;i<size;i++){
60.                 printf("%d",ret[i]);
61.         }
62.         return 0;
63. }

复制代码

后续继承更新…

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。