研究研究算法--贪心算法

一、什么是贪心算法

贪心算法是针对每一次循环而言的。对于每一次计算,都尽量选择最优的解。

二、自己做的一个ACM题目(poj1328)

题外话,当年真该参加ACM竞赛,希望为时不晚

1.看题

题目大意:
 地图的x轴的上方为海,下方为陆地,海中有n个小岛,坐标为(isl[i].x,isl[i].y)。
 有一种雷达,能探测到的范围为以R为半径的圆。
 问海岸线上至少造多少雷达可以把所有的小岛都包含在内。

2.思路

对于每一个岛屿,我们都假设有对应的雷达能扫描到(贪心),并求出其在X轴上能够部署雷达的范围。最后,两两比较,去掉区域相互覆盖的范围,就是最终的结果了。

3.C语言实现

#include "stdio.h"
#include "stdbool.h"
#include "math.h"

// 岛屿在海岸线的范围
typedef struct {
  double left,right;
  bool isOverlay;
} XRange;

// 岛屿坐标
typedef struct {
  int x,y;
  XRange range;
} Island;
// 半径
#define R 111

Island * computedRange(Island * land);
bool isOverlay(Island * land1,Island * land2);


int main(int argc, char const *argv[]) {
  // 数量
  int num = 0;
  // 岛屿坐标
  Island lands[] = {
    {820,55},
    {34,44},
    {56,22},
    {32,11},
    {57,78},
    {-157,22},
    {-23,65},
    {-555,88},
    {-222,10},
    {-111,90},
  };

  // 初始化岛屿结构体
  for(int i=0;i<sizeof(lands)/sizeof(lands[0]);i++){
    // y坐标需小于等于半径R
    if(lands[i].y - R > 0 || lands[i].y<0){
      printf("%s\n", "there is no result!");
      return 0;
    }
    lands[i].range.isOverlay = false;
    computedRange(&lands[i]);
  }

  // 遍历范围,计算是否重叠
  for(int i=0;i<sizeof(lands)/sizeof(lands[0]);i++){
    Island land = lands[i];
    // 只遍历没有重叠区的范围
    if(land.range.isOverlay){
      break;
    }
    if(i==sizeof(lands)/sizeof(lands[0])-1){
      break;
    }
    for(int j=i+1;j<sizeof(lands)/sizeof(lands[0]);j++){
      if(isOverlay(&lands[i],&lands[j])){
        lands[j].range.isOverlay = true;
      }
    }
  }

  // 打印结果
  for(int i=0;i<sizeof(lands)/sizeof(lands[0]);i++){
    printf("%f %f %f %d\n", lands[i].range.left,lands[i].range.right,lands[i].range.right-lands[i].range.left,lands[i].range.isOverlay);
    if(lands[i].range.isOverlay==0){
      num++;
    }
  }
  printf("needs number : %d\n", num);
  return 0;
}


// 计算岛屿在X轴的对应的范围
Island * computedRange(Island * land){
  int x = land->x;
  int y = land->y;
  land->range.left = x-sqrt(pow(R,2)-pow(y,2));
  land->range.right = sqrt(pow(R,2)-pow(y,2))+x;
  return land;
}

// 判断重叠
bool isOverlay(Island * land1,Island * land2){
  if((land1->range.right<=land2->range.right && land1->range.right>=land2->range.left)
    || (land2->range.right<=land1->range.right && land2->range.right>=land1->range.left)
  ){
    return true;
  }else
    return false;
}

编译输出如下:

gcc main.c -o out
./out
723.584234 916.415766 192.831533 0
-67.906820 135.906820 203.813640 0
-52.797978 164.797978 217.595956 1
-78.453610 142.453610 220.907220 1
-21.974679 135.974679 157.949359 1
-265.797978 -48.202022 217.595956 1
-112.977775 66.977775 179.955550 1
-622.653529 -487.346471 135.307058 0
-332.548632 -111.451368 221.097264 0
-175.969223 -46.030777 129.938447 1
needs number : 4

注释比较清楚,看看就明白了,不做累赘解释了。

三、结论

写程序的时候或许你不知道这就叫做贪心算法,说明你是个老手,算法就在心中。

四、网上找的其他类似题目(有空的朋友,也可以用程序来实现)

1.线段覆盖

在一维空间中告诉你N条线段的起始坐标与终止坐标,要求求出这些线段一共覆盖了多大的长度。

2.数字组合问题

输入一个数字M,以及N个数字(位数不限),程序将这N个数字随机组合,算出不超过M的最大数的组合

3.会议室安排

有N个活动时间集合,每个活动都要使用同一个会议场,而且同一时间内只能有一个活动使用。每个活动都有一个使用活动的开始si和结束时间fi,即他的使用区间为(si,fi)。现在要求你分配活动占用时间表,即哪些活动占用该会议室,哪些不占用,使得他们不冲突,要求是尽可能多的使参加的活动最大化,即所占时间区间最多。

有其他的欢迎补充

本文完



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注