贪心算法应用例题

最优装载问题

#include <stdio.h>
#include <algorithm>//排序int main()
{int data[] = { 8,20,5,80,3,420,14,330,70 };//物体重量int max = 500;//船容最大总重量int count = sizeof(data) / sizeof(data[0]);//物体数量std::sort(data, data + count);//排序,排完数组中的数据从小到大排列int tmp = 0;//记总重量加和int n = 0;//记物体总件数for (int i = 0; i < count; i++)//从小到大，从轻到重挨个放进去{tmp += data[i];if (tmp > max){break;}n++;}printf("%d\n", n);return 0;}

#include <stdio.h>
//给的数字是否能种下
bool canPlaceFlowers(int* data, int datasize, int n)//数组。数组长度，给的数字
{int i=0;//数组下标从0开始if (n == 0)//一朵不种{return true;//能}int count = 0;while (i < datasize)//在种地（数组）的长度里面{if (data[i] == 1)//当前有花1{i += 2;//空1再种01}else if (i > 0 && data[i - 1] == 1)//左边有花，当前没花0{i += 1;//1}else if (i + 1 < datasize && data[i + 1] == 1)//右边有花，当前没花0{i += 3;//101}else{//data[i]=1;种花，可不种，本题只要求数数字count++;//可种花空地+1i += 2;//空1再种01,类似if1if (count == n)//一等于就能，可大于{return true;}}}//条件都过一遍，i+到相应位置，符合while再进，不符若count<n就错return false;}int main()
{int data[] = { 1,0,0,0,1,0,0,0,0,0,0,1 };//顺序种逆序种最大count都是3if (canPlaceFlowers(data, sizeof(data) / sizeof(data[0]), 3)){printf("可以！\n");//return true;}else{printf("不可以！\n");}return 0;
}

例如：

输出【5,10】

相邻距离近的先发生碰撞

输出为空，全爆炸完了

输出【10】

#include <stdio.h>
#include <math.h>
#include <stdlib.h>//碰撞爆炸函数
int* collision(int* data, int dataSize, int* retSize)//行星数组，数组大小（行星个数），碰炸后输出的数组
{int n = 0;//记录爆炸的个数while (1)//{int pre = 0;//左边行星下标int next = 1;//右边行星下标while (next < dataSize)//在数组内{if (data[pre] * data[next] < 0)//左右行星异号，方向相反{if (data[pre] < 0)//左边行星向左，则右向右，左右远离{//pre++;这样会有bug，pre可能走到爆炸过的0位置//next++;//移到下一个比较位置pre = next;//跳过中间可能有的0next++;continue;//跳出重进while (next < dataSize)}//左右相接近，3种爆炸情况，左没（变0），右没，左右都没if (abs(data[pre]) > abs(data[next]))//左绝对值大于右，abs求绝对值头函数math.h{data[next] = 0;//右炸没变0n++;}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] * data[next] < 0)}//爆炸完出现0后的位置移动，3种if (data[pre] == 0){pre = next;next++;}else if (data[next] == 0)//[next==0]--[10,2]{next++;}else{pre = next;next++;}}if (next >= dataSize)//出数组，出while {break;}}*retSize = dataSize - n;//输出数组大小int* retArray = (int*)malloc(*retSize * sizeof(int));//动态申请数组for (int i = 0, k = 0; i < dataSize; i++)//遍历原数组{if (data[i]!=0)//data[i]不为0，为真，也可if (data[i]）{retArray[k++] = data[i];//数组不为0粘贴}}return retArray;
}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;
}