浅谈Python实现贪心算法与活动安排问题

贪心算法

原理：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

特性：贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质。

如题：给出一组活动，告诉每个活动的开始时间和结束时间，要求出算出能参加的最多活动的数量或者活动的起止时间

贪心算法思路：

用两个数组s，f分别存储活动的起止时间，根据活动的结束时间对活动进行一个非减的活动序列，同样活动的开始时间list也要做对应的调整，这里博主是通过冒泡排序同步交换的，举例：活动（1，4）（2，3）（3，5）那么我们得到的

s = [2,1,3]
f = [3,4,5]

通过比较下一个活动的开始时间与上一个活动的结束时间的大小关系，确定这两个活动是否是相容的，如果开始时间大于结束时间，则相容，反之不相容,代码如下

#用冒泡排序对结束时间进行排序，同时得到对应的开始时间的list
def bubble_sort(s,f):
  for i in range(len(f)):
    for j in range(0,len(f)-i-1):
      if f[j] > f[j+1]:
        f[j], f[j+1] = f[j+1],f[j]
        s[j],s[j+1] = s[j+1],s[j]
  return s,f

def greedy(s,f,n):
  a = [True for x in range(n)]
  #初始选择第一个活动
  j = 0
  for i in range(1,n):
    #如果下一个活动的开始时间大于等于上个活动的结束时间
    if s[i] >= f[j]:
      a[i] = True
      j = i
    else:
      a[i] = False
  return a

n = int(input())
arr = input().split()
s = []
f = []
for ar in arr:
  ar = ar[1:-1]
  start = int(ar.split(',')[0])
  end = int(ar.split(',')[1])
  s.append(start)
  f.append(end)

s,f = bubble_sort(s,f)
A = greedy(s,f,n)

res = []
for k in range(len(A)):
  if A[k]:
    res.append('({},{})'.format(s[k],f[k]))
print(' '.join(res))

执行结果如下：输入11个活动的起止时间，输出相容的活动的起止时间

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python基于贪心算法解决背包问题示例

    本文实例讲述了Python基于贪心算法解决背包问题.分享给大家供大家参考,具体如下: 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 完全背包问题:给定n个物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,背包问题是如何选择入背包

  • 浅谈Python实现贪心算法与活动安排问题

    浅谈Python实现贪心算法与活动安排问题

    贪心算法 原理:在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解.贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解. 特性:贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不

  • C++贪心算法实现活动安排问题(实例代码)

    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 具体代码如下所示: #include <cstdio> #include <iostream> #include <ctime> #include <

  • 浅谈python常用程序算法

    一.冒泡排序: 1.冒泡排序是将无序的数字排列成从小到大的有序组合: 过程:对相邻的两个元素进行比较,对不符合要求的数据进行交换,最后达到数据有序的过程. 规律: 1.冒泡排序的趟数时固定的:n-1 2.冒泡排序比较的次数时固定的:n*(n-1)/2 3.冒泡排序交换的次数时不固定的:但是最大值为:n*(n-1)/2 注意:n = 数据个数,排序过程中需要临时变量存储要交换的数据 eg: l=[688, 888, 711,999,1,4,6] for i in range(len(l)-1):

  • 浅谈Python实现Apriori算法介绍

    浅谈Python实现Apriori算法介绍

    导读: 随着大数据概念的火热,啤酒与尿布的故事广为人知.我们如何发现买啤酒的人往往也会买尿布这一规律?数据挖掘中的用于挖掘频繁项集和关联规则的Apriori算法可以告诉我们.本文首先对Apriori算法进行简介,而后进一步介绍相关的基本概念,之后详细的介绍Apriori算法的具体策略和步骤,最后给出Python实现代码. 1.Apriori算法简介 Apriori算法是经典的挖掘频繁项集和关联规则的数据挖掘算法.A priori在拉丁语中指"来自以前".当定义问题时,通常会使用先验知识

  • 浅谈Python数学建模之线性规划

    浅谈Python数学建模之线性规划

    目录 一.求解方法.算法和编程方案 1.1.线性规划问题的求解方法 1.2.线性规划的最快算法 1.3.选择适合自己的编程方案 二.PuLP库求解线性规划问题 2.1.线性规划问题的描述 2.2.PuLP 求解线性规划问题的步骤 2.3.Python例程:线性规划问题 三.小结 一.求解方法.算法和编程方案 线性规划 (Linear Programming,LP) 是很多数模培训讲的第一个算法,算法很简单,思想很深刻. 线性规划问题是中学数学的内容,鸡兔同笼就是一个线性规划问题.数学规划的题目在

  • 浅谈Python数学建模之数据导入

    目录 一.数据导入是所有数模编程的第一步 二.在程序中直接向变量赋值 2.1.为什么直接赋值? 2.2.直接赋值的问题与注意事项 三.Pandas 导入数据 3.1.Pandas 读取 Excel 文件 3.2.Pandas 读取 csv 文件 3.3.Pandas 读取文本文件 3.4.Pandas 读取其它文件格式 四.数据导入例程 一.数据导入是所有数模编程的第一步 编程求解一个数模问题,问题总会涉及一些数据. 有些数据是在题目的文字描述中给出的,有些数据是通过题目的附件文件下载或指定网址

  • 浅谈python中copy和deepcopy中的区别

    在下是个编程爱好者,最近将魔爪伸向了Python编程.....遇到copy和deepcopy感到很困惑,现在针对这两个方法进行区分,一种是浅复制(copy),一种是深度复制(deepcopy). 首先说一下deepcopy,所谓的深度复制,在这里我理解的是完全复制然后变成一个新的对象,复制的对象和被复制的对象没有任何关系,彼此之间无论怎么改变都相互不影响. 然后说一下copy,在这里我分为两类来说,一种是字典数据类型的copy函数,一种是copy包的copy函数. 一.字典数据类型的copy函数

  • 浅谈python中的数字类型与处理工具

    浅谈python中的数字类型与处理工具

    python中的数字类型工具 python中为更高级的工作提供很多高级数字编程支持和对象,其中数字类型的完整工具包括: 1.整数与浮点型, 2.复数, 3.固定精度十进制数, 4.有理分数, 5.集合, 6.布尔类型 7.无穷的整数精度 8.各种数字内置函数及模块. 基本数字类型 python中提供了两种基本类型:整数(正整数金额负整数)和浮点数(注:带有小数部分的数字),其中python中我们可以使用多种进制的整数.并且整数可以用有无穷精度. 整数的表现形式以十进制数字字符串写法出现,浮点数带

  • 浅谈python迭代器

    1.yield,将函数变为 generator (生成器) 例如:斐波那契数列 def fib(num): a, b, c = 1, 0, 1 while a <= num: yield c b, c = c, b + c a += 1 for n in fib(10): print(n, end=' ') # 1 1 2 3 5 8 13 21 34 55 2.Iterable 所有可以使用for循环的对象,统称为 Iterable (可迭代) from collections import

  • 浅谈Python对内存的使用（深浅拷贝）

    本文主要研究的是Python对内存的使用(深浅拷贝)的相关问题,具体介绍如下. 浅拷贝就是对引用的拷贝(只拷贝父对象) 深拷贝就是对对象的资源的拷贝 >>> a=[1,2,3,'a','b'] >>> b=a >>> b [1, 2, 3, 'a', 'b'] >>> a [1, 2, 3, 'a', 'b'] >>> id(a) 3021737547592 >>> id(b) 3021737547

随机推荐