贪心算法笔记

贪心算法

根据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;
}

后续继续更新…

原文地址：https://blog.csdn.net/qq_45190745/article/details/142965285

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！