贪心算法笔记

贪心算法

根据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，问：最大装几件宝物？

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

算法2（初级）：

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

#include<stdio.h>bool canZ(int *data, int n){int i;int datasize=sizeof(data)/sizeof(data[0]);if (n==0) return true;int count=0;while(i<datasize){if(data[i]==1) i+=2;else if(i>0&data[i-1]==1) i+=1;// 左边有花，走一步else if(i+1<datasize&data[i+1]==1) i+=3; // 右边有花，走三步esle return true;}return false;
}int main(){int *data={1,0,0,0,1,0,1,0,0,0,0,0,1}if(canZ(data,4)) cout<<"OK";else cout<<"NO";return 0;
}

算法3（中级）：

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

#include<stdio.h>
#include<stdlib.h>
#include<math.h>int *collision(int *data,int datasize,int *retsize){int n=0;//记录爆炸次数while(1){int pre=0;int next=0;while(next<datasize){if(data[pre]*data[next]<0){ // 运动方向相反if(data[pre]<0){ // 左边向左，右边想右，不会碰撞pre=next;next++;continue;}}				else if(abs(data[pre]) < abs(data[next])){ // 发生碰撞了，小的爆炸data[next]=0;n++;}else if(abs(data[pre]) > abs(data[next])){ // 发生碰撞了，小的爆炸data[pre]=0;n++;}else { // 发生碰撞了，相同大小的爆炸data[pre]=0;data[next]=0;n+=2;}break;	}if(data[pre]==0){ // 左边已经碰撞了pre=next;next++;}else if(data[next]==0){ // 右边已经碰撞了next++;}else{ // 方向相同pre=next;next++;}if(next>=datasize)break;}int *retsize=datasize-n;int *retArray=(int *)malloc(*retsize * sizeof(int)); // 分配一个存储数组for(int i=0,k=0;i<size;i++){if(data[i])retArray[k++]=data[i];}
}int main(){int data[]={10,2,-5};int size;int *ret=collision(data,3,&size);for(int i=0;i<size;i++){printf("%d",ret[i]);}return 0;
}