个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 30 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章贪心算法的C语言实现与运用详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

贪心算法 。

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

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

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

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

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

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

  。

实现该算法的过程:

从问题的某一初始解出发； 。

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

do 求出可行解的一个解元素； 。

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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是兼容的。活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。 将所有的活动按照结束时间升序排列 。

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

  。

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

ac代码 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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语言实现与运用详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

30 4 0
文章推荐： SQLServer2005混合模式登录配置(用户登录错误18452,233,4064)
文章推荐： sql server 2005因架构无法删除用户错误15138的解决方法
文章推荐： 安装SqlServer2005时版本变更检查 (警告)
文章推荐： Win2008中安装的MSSQL2005后无法访问的解决方法
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com