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

187 浏览量更新于2023-03-16 评论 1 收藏 59KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

本篇文章主要介绍了浅谈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个活动的起止时间，输出相容的活动的起止时间

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38623255

粉丝: 4
资源: 919

会员权益专享

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

评论0

会员权益专享

最新资源

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

评论0

活动安排问题之贪心算法

贪心算法python实现

活动安排问题（贪心算法）

python qubon贪心算法

python 实现贪心算法

python实现贪心算法

python实现贪心算法例子

python+贪心算法

贪心算法实现活动安排问题

python qubo

用python语言实现活动安排问题的贪心算法

python用贪心算法实现背包问题

python贪心算法活动安排

使用python实例实现贪心算法的具体过程

python贪心算法活动安排活动时间短优先

用Python写贪心算法

写出贪心算法求活动安排问题的python的代码

python贪心算法迷宫

使用贪心算法求解活动安排问题

使用python进行贪心算法

会员权益专享

最新资源