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

yipeiwu_com5年前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个活动的起止时间,输出相容的活动的起止时间


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python实现类似比特币的加密货币区块链的创建与交易实例

Python实现类似比特币的加密货币区块链的创建与交易实例

虽然有些人认为区块链是一个早晚会出现问题的解决方案,但是毫无疑问,这个创新技术是一个计算机技术上的奇迹。那么,究竟什么是区块链呢? 区块链 以比特币(Bitcoin)或其它加密货币按...

代码分析Python地图坐标转换

最近做项目正好需要坐标的转换 各地图API坐标系统比较与转换; WGS84坐标系:即地球坐标系,国际上通用的坐标系。设备一般包含GPS芯片或者北斗芯片获取的经纬度为WGS84地...

Python语法之精妙的十个知识点(装B语法)

Python 是一种代表简单思想的语言,其语法相对简单,很容易上手。不过,如果就此小视 Python 语法的精妙和深邃,那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的...

利用Python获取操作系统信息实例

前言 每一位运维人员都应该对自己所管理的机器配置很清楚,因为这对我们快速处理问题很有帮助,比如随着业务增长,突然某些机器负载上涨的厉害,这时候要排查原因,除了从应用程序、架构上分析外,当...

Python基于pycrypto实现的AES加密和解密算法示例

本文实例讲述了Python基于pycrypto实现的AES加密和解密算法。分享给大家供大家参考,具体如下: 一 代码 # -*- coding: UTF-8 -*- import s...