ToB企服应用市场:ToB评测及商务社交产业平台

标题: 贪心算法笔记 [打印本页]
作者: 干翻全岛蛙蛙    时间: 2024-10-24 14:04
标题: 贪心算法笔记
贪心算法

根据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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4