贪心算法的C语言实现与运用详解_C 语言

贪心算法

所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下:

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解,得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

 

实现该算法的过程:

从问题的某一初始解出发;

 while 能朝给定总目标前进一步

do 求出可行解的一个解元素;

由所有解元素组合成问题的一个可行解;

#include "stdio.h"
void main()
{
   int act[11][3]={{1,1,4},{2,3,5},{3,0,6},{4,5,7},{6,5,9},
   {7,6,10},{8,8,11},{9,8,12},{10,2,13},{11,12,14}};
   greedy(act,11);
   getch();
}
int greedy(int *act,int n)
{
   int i,j,no;
   j=0;
   printf("Selected activities:/n");
   no=0;
   printf("Act.%2d: Start time %3d, finish time %3d/n", act[no],act[no+1],act[no+2]);
  for(i=1;i<n;i++)
  {
    no=i*3;
    if(act[no+1]>=act[j*3+2])
       {
         j=i;
         printf("Act.%2d: Start time %3d, finish time %3d/n",    act[no],act[no+1],act[no+2]);
       }
    }
 }

 例题

    题目描述: 
    又到毕业季,很多大公司来学校招聘,招聘会分散在不同时间段,小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。 
    输入: 
    第一行n,有n个招聘会,接下来n行每行两个整数表示起止时间,由从招聘会第一天0点开始的小时数表示。 
    n <= 1000 。 
    输出: 
    最多参加的招聘会个数。 
    样例输入: 
    3 
    9 10 
    10 20 
    8 15 
    样例输出: 
    2 

活动选择问题
概述
这个问题是对几个相互竞争的招聘会活动进行调度,它们都要求以独占的方式使用某一公共资源(小明)。调度的目标是找出一个最大的相互兼容的活动集合。这里是有一个需要使用某一资源(小明)的n个活动组成的集合S={a1,a2,...,an}.该资源一次只能被一个活动占用。每个活动ai有开始时间si和结束时间fi,且0<=si<fi<无穷。一旦被选择后,活动ai就占据了区间[si,fi].如果区间[si,fi]和[sj,fj]互不重叠,称活动ai和aj是兼容的。活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。
将所有的活动按照结束时间升序排列

定理
对于任意非空子问题Sij,设am是Sij中具有最早结束时间的活动:
fm=min{fk:ak属于Sij}
那么,
1)活动am在Sij的某最大兼容活动子集中被使用
2)子问题Sim为空,所以选择am将使子问题Smj为唯一可能非空的子问题

ac代码

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h> 

  struct join
  {
    int begin;
    int end;
  }; 

  int compare(const void *a, const void *b); 

  int main()
  {
    int i, n, k;
    struct join joins[1001], temp[1001]; 

    while(scanf("%d", &n) != EOF)
    {
      for(i = 0; i < n; i ++)
      {
        scanf("%d %d", &joins[i].begin, &joins[i].end);
      } 

      qsort(joins, n, sizeof(joins[0]), compare); 

      k = 0;
      temp[k] = joins[0];
      for(i = 1; i < n; i ++)
      {
        if(joins[i].begin >= temp[k].end)
          temp[++ k] = joins[i];
      }
      printf("%d\n", k + 1);
    } 

    return 0;
  } 

  int compare(const void *a, const void *b)
  {
    const struct join *p = a;
    const struct join *q = b; 

    return p->end - q->end;
  }

    /**************************************************************
        Problem: 1463
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:10 ms
        Memory:904 kb
    ****************************************************************/ 

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索c语言
贪心算法
c语言贪心算法、c语言贪心算法tsp、贪心算法实例c语言、贪心算法详解、fft算法c语言实现详解,以便于您获取更多的相关知识。

时间: 2024-12-10 02:01:33

贪心算法的C语言实现与运用详解_C 语言的相关文章

C语言柔性数组实例详解_C 语言

本文实例分析了C语言柔性数组的概念及用法,对于进一步学习C程序设计有一定的借鉴价值.分享给大家供大家参考.具体如下: 一般来说,结构中最后一个元素允许是未知大小的数组,这个数组就是柔性数组.但结构中的柔性数组前面必须至少一个其他成员,柔性数组成员允许结构中包含一个大小可变的数组,sizeof返回的这种结构大小不包括柔性数组的内存.包含柔数组成员的结构用malloc函数进行内存的动态分配,且分配的内存应该大于结构的大小以适应柔性数组的预期大小.柔性数组到底如何使用? 不完整类型 C和C++对于不完

C语言for语句用法详解_C 语言

首先,这里所提到的类C语言指的是如C.C++.C#和Java等语法和C语言一样或类似的程序设计语言.这些语言中,for语句的语法和执行流程都是一样的.本文将就这一语句的用法进行一个较为深入的讨论. for语句: 复制代码 代码如下: for (表达式1;表达式2;表达式3) {   循环语句 } 表达式1 给循环变量赋初值 表达式2 为循环条件 表达式3 用来修改循环变量的值,称为循环步长. for语句的执行流程: 例:编程计算:1+2+3+...+99+100的结果. 这是累加问题,累加问题的

C语言关系运算符实例详解_C 语言

在程序中经常需要比较两个数据的大小,以决定程序下一步的工作.比如一个程序限制了只能成年人使用,儿童因为年龄不够,没有权限使用.这时候程序就需要获取用户输入的年龄并做出判断,如果超过18岁就正常运行,否则给出无权使用的提示. 比较两个数据大小的运算符称为关系运算符(Relational Operators). 在C语言中有以下关系运算符: 1) <(小于) 2) <=(小于或等于) 3) >(大于) 4) >=(大于或等于) 5) ==(等于) 6) !=(不等于) 关系运算符都是双

C语言 格式化读写文件详解_C 语言

fscanf() 和 fprintf() 函数与前面使用的 scanf() 和 printf() 功能相似,都是格式化读写函数,两者的区别在于 fscanf() 和 fprintf() 的读写对象不是键盘和显示器,而是磁盘文件. 这两个函数的原型为: int fscanf ( FILE *fp, char * format, ... ); int fprintf ( FILE *fp, char * format, ... ); fp 为文件指针,format 为格式控制字符串,... 表示参数

你必须知道的C语言预处理的问题详解_C 语言

C语言预处理器执行宏替换.条件编译和文件包含.通常采用以"#"为行首的提示.下面是C语言预处理的应用场合: 1.三字母词(Trigraph Sequences) C源程序的字符集被包含在7位的ASCII字符集中,但是它是ISO 646-1983 Invariant Code Set的超集.为了让程序可以在缩减集(reduced set)中呈现出来,下面的三字母词会被替换成相应的单字符. 三字母词 单字符 ??= # ??/ \ ??' ^ ??( [ ??) ] ??! | ??<

C语言内存对齐实例详解_C 语言

本文详细讲述了C语言程序设计中内存对其的概念与用法.分享给大家供大家参考之用.具体如下: 一.字节对齐基本概念 现代计算机中内存空间都是按照byte划分的,从理论上讲似乎对任何类型的变量的访问可以从任何地址开始,但实际情况是在访问特定类型变量的时候经常在特定的内存地址访问,这就需要各种类型数据按照一定的规则在空间上排列,而不是顺序的一个接一个的排放,这就是对齐. 对齐的作用和原因:各个硬件平台对存储空间的处理上有很大的不同.一些平台对某些特定类型的数据只能从某些特定地址开始存取.比如有些架构的C

C语言格式化输入输出函数详解_C 语言

一:格式输出函数printf() 1.调用形式一般为:printf("格式化控制字符串",输出表列): 2.格式化控制字符串用于指定输出格式,它有三种形式: 1.格式说明符:规定了相应输出表列内容的输出格式,以%打头,如%d.%o等 2.转义字符:用来输出转义字符所代表的控制代码或者特殊字符,比如常用的'\n'.'\t' 3.普通字符:需要原样输出的字符. 3.输出表列为若干需要输出的数据项,它与格式说明符在数量和类型上一一对应: 4.格式字符m指定输出数据所占宽度,n对实数表示输出n

基于C语言string函数的详解_C 语言

PS:本文包含了大部分strings函数的说明,并附带举例说明.本来想自己整理一下的,发现已经有前辈整理过了,就转了过来.修改了原文一些源码的问题,主要是用char *字义字符串的问题,导致程序运行时崩溃.另外自己重写了部分测试程序,使其更能满足自己测试的需要.不当之处,还请海涵.@函数原型:  char *strdup(const char *s) 函数功能:  字符串拷贝,目的空间由该函数分配  函数返回:  指向拷贝后的字符串指针 参数说明:  src-待拷贝的源字符串 所属文件:  <s

数据结构之伸展树详解_C 语言

1. 概述 二叉查找树(Binary Search Tree,也叫二叉排序树,即Binary Sort Tree)能够支持多种动态集合操作,它可以用来表示有序集合.建立索引等,因而在实际应用中,二叉排序树是一种非常重要的数据结构. 从算法复杂度角度考虑,我们知道,作用于二叉查找树上的基本操作(如查找,插入等)的时间复杂度与树的高度成正比.对一个含n个节点的完全二叉树,这些操作的最坏情况运行时间为O(log n).但如果因为频繁的删除和插入操作,导致树退化成一个n个节点的线性链(此时即为一个单链表