`

贪心算法,动态规划 源码解析

阅读更多

贪心算法讲解例题:活动选择问题问题描述

有一个需要使用每个资源的n个活动组成的集合S= {a1,a2,···,an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间,且 0<= s < f < 。一旦被选择后,活动a就占据半开时间区间[s,f]。如果[s,f]和[s,f]互不重叠,则称两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。

11个活动按结束时间排序好,之后为:

s[]={1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; //开始时间

f[]={4, 5, 6, 7, 8, 9,10,11,12, 13,14}; //结束时间(递增)

动态规划求解:O(n3)

#include"stdio.h"
int c[13][13];//活动的个数 用来表示 从 i 到 j 符合规则的有几个活动
int partition[13][13];//partition[i][j] 表示 使用哪个k 使得s[i][j]到最大兼容集合

void dynamic_Activity_select(int s[],int f[],int n)
{
int i,j,k;
for(i=0;i<=n;i++)//初始化 情况下 没有一个活动
for(j=0;j<=n;j++)
{
if(i==j)
c[i][j]=1;// 这个地方其实很关键 ,往往 贪心求解时 初始化容易初始化为 0
else
c[i][j]=0;
}

for(i=1;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(i>=j) //前面的 活动不能超过后面的活动
c[i][j]=0;
else
{
for(k=i+1;k<=j-1;k++) //从前面的下一个 活动开始
{
if(s[k] >= f[i] && f[k] <= s[j])// k 开始后 i 结束 k 结束 s 还没有开始
if(c[i][j]<c[i][k]+c[k][j]+1)
{
c[i][j]=c[i][k]+c[k][j]+1;
partition[i][j]=k;
}
}
}
}
}
}

int main()
{
int s[]={0,1,3,0,5,3,5,6,8,8,2,12}; //这个地方容易出错
int f[]={0,4,5,6,7,8,9,10,11,12,13,14};
dynamic_Activity_select(s,f,11);
int m=11;
int n=11;

for(int i=1;i<n;i++) //这里可以自定义输出
{
for (int j=1;j<m;j++)
printf("%3d", partition[i][j]);

printf("\n");
}
}
<wbr></wbr>


由于动态规划时间复杂度高,用来求解这类问题,大材小用。所以提供以下贪心算法

#include"stdio.h"

void recursive_activity_select(int s[],int f[],int i,int n)//递归的贪心算法
{
int m=i+1;
while(m<=n&&s[m]<f[i]) //找出第一个符合条件的 (有时候第一个并不是符合条件的)
m++;

if(m<=n)
{
printf("%4d",m);
recursive_activity_select(s,f,m,n);

}
else
return ;

}
/*这个方法思想:寻找最早结束且与前一个 兼容的 活动加入集合 i 在前 m 在后*/
void greedy_activity_select(int s[],int f[],int n)//迭代方法
{
int i=1;
/*由于是按照最早结束时间来排序 所以第一个肯定是最早结束的活动*/
printf("%4d",1);
for(int m=2;m<=n;m++) //也可以按照递归方法 中使用 while 循环(一个道理)
{
if(s[m]>=f[i])
{
printf("%4d",m);
i=m;
}
}
}
int main()
{
int s[]={0,1,3,0,5,3,5,6,8,8,2,12}; //这个地方容易出错
int f[]={0,4,5,6,7,8,9,10,11,12,13,14};
printf("要选择的活动为:");
// recursive_activity_select(s,f,0,11);//之所以注释掉 是因为跟下面的方法重复 一次只能调试一个
greedy_activity_select(s,f,11);
}

评论这张
转发至微博
转发至微博
分享到:
评论

相关推荐

    C语言实现贪心算法(源码+解析)

    贪心算法函数 greedyKnapsack:使用贪心策略解决背包问题。首先对物品按照性价比排序,然后从性价比最高的物品开始放入背包,直到背包装满或者物品放完。如果某个物品无法完全放入背包,则按比例放入。 主函数 main...

    C#贪心算法-找钱问题源码

    下面我们将详细探讨C#实现贪心算法找钱问题的关键步骤、算法逻辑以及源码解析。 首先,我们需要定义问题的数据结构。通常,这包括硬币的面值数组和需要找零的总金额。在C#中,可以这样表示: ```csharp int[] ...

    算法设计与分析部分背包贪心算法是源码

    ### 算法设计与分析:部分背包贪心算法源码解析 在计算机科学与算法设计领域,背包问题是一类经典的优化问题,旨在解决如何在有限的资源(如背包容量)下选择物品(每个物品有特定的价值和重量),使得所选物品的总...

    前端总结、手写代码、数据结构与算法 Leetcode、源码解析.zip

    6. **贪心算法**:每一步都采取局部最优解,期望整体最优,如Prim算法(最小生成树)。 7. **分治算法**:将大问题分解为小问题求解,然后合并结果,如归并排序、快速排序等。 三、LeetCode LeetCode是一个在线...

    排课系统源码以及贪心算法思想详解.rar

    排课系统源码以及贪心算法思想详解是一个深入解析如何运用C语言实现数据结构与算法在实际问题中的应用,特别是针对高校排课系统的实例。在这个压缩包中,包含了一个排课系统的基础源码,以及对贪心算法的详细解释,...

    自主探索算法的源码解析

    总结来说,自主探索算法的源码解析涉及到环境感知、路径规划、决策制定等多个层面,对于理解和开发ROS中的机器人探索系统至关重要。通过深入学习和实践,我们可以提升机器人在未知环境中的智能行为,推动机器人技术...

    排课系统源码以及贪心算法思想详解.rar_rezip.zip

    排课系统源码以及贪心算法思想详解是一个深入解析如何运用C语言实现数据结构与算法在实际问题中的应用,特别是针对高校排课系统的实例。在这个压缩包中,包含了一个排课系统的基础源码,以及对贪心算法的详细解释,...

    排课系统源码以及贪心算法思想详解.rar_rezip1.zip

    排课系统源码以及贪心算法思想详解是一个深入解析如何运用C语言实现数据结构与算法在实际问题中的应用,特别是针对高校排课系统的实例。在这个压缩包中,包含了一个排课系统的基础源码,以及对贪心算法的详细解释,...

    程序员实用算法 pdf+源码

    10. **源码解析**:书中提供的源码有助于读者更直观地理解算法的实现过程,通过实际运行和调试代码,可以提高对算法的掌握程度。 总之,《程序员实用算法》是一本覆盖全面、实例丰富的学习资源,无论是初学者还是...

    基于javaScript实现的百度地图旅行路径规划算法+源码+项目文档+算法流程解析+功能介绍(毕业设计&课程设计&项目开发)

    基于javaScript实现的百度地图旅行路径规划算法+源码+项目文档+算法流程解析+功能介绍,适合毕业设计、课程设计、项目开发。项目源码已经过严格测试,可以放心参考并在此基础上延申使用~ 项目简介: 旅行路径规划...

    田忌赛马: POJ 2287(贪心解法)

    贪心算法是一种在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。在POJ 2287题中,我们需要通过贪心策略来解决赛马比赛的胜负问题。 首先,我们来看一下题目...

    50个经典C语言算法源码及解析说明.rar

    《50个经典C语言算法源码及解析说明》是一个非常宝贵的资源,它涵盖了C语言编程中的各种核心算法。这个压缩包包含了一份名为"51CTO下载-经典c算法.txt"的文件,很可能是对这50个算法的详细解释和源代码的列表。下面...

    数据结构算法及解析 高一凡

    高一凡在书中强调了算法的重要性,并系统地介绍了算法设计的基本方法,包括贪心算法、分治算法、动态规划、回溯算法等。每种算法都配以具体的实例,帮助读者理解其思想和应用情境。此外,书中还详细讲解了算法的效率...

    采用贪心法求解着色问题(JAVA)

    在这个问题中,我们使用贪心算法来解决,这是一种局部最优策略,每次选择当前最优的解决方案,并希望最终得到全局最优解。以下是对贪心法求解着色问题的详细解析。 ### 贪心算法原理 贪心算法是一种在每一步选择...

    《算法竞赛宝典》全部配套资源(非侵权)

    1. **题目集**:涵盖各种类型的算法问题,如排序、搜索、图论、动态规划、贪心算法等。这些题目可以帮助读者熟悉各种算法的应用场景,并通过实践提高解题能力。 2. **解题思路**:对于每个题目,都可能有详细的解题...

    严蔚敏版数据结构算法源码(高一凡)

    此外,源代码还可能包含一些高级主题,如图的遍历算法(深度优先搜索和广度优先搜索)、动态规划问题的解决、贪心策略的应用等。通过这些源代码,学习者可以更深入地了解数据结构与算法的原理,为解决复杂计算问题...

    java经典算法90题含源码及答案.rar

    在JAVA经典算法40题.doc中,可能包含的题目类型有递归、分治、贪心、回溯、动态规划等。例如,经典的二分查找、快速排序、斐波那契数列、最小路径和等问题,都是锻炼算法思维的好例子。每道题目的解答通常会涉及到对...

    【超全!】图解Java数据结构和算法(共195集)【资料+视频+课件+代码+笔记】

    稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式...动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法...

    机器学习C++源码解析-Adaboost算法-源码+数据

    2. 弱学习器:实现决策树或stump的训练和预测函数,这部分可能需要利用贪心策略来快速找到最佳划分点。 3. 误差计算:计算每个弱分类器的误分类率,用于确定其权重。 4. 权重更新:根据弱分类器的性能更新样本权重,...

    数学建模10大算法详解+程序源码打包.rar

    《数学建模10大算法详解+程序源码打包》是一个专门为数学建模初学者准备的资源包,其中包含了丰富的算法解析和实际的程序代码,旨在帮助初学者深入理解和应用数学建模中的核心算法。以下是这十大算法的详细介绍: 1...

Global site tag (gtag.js) - Google Analytics