快捷導(dǎo)航

淺談Python實(shí)現(xiàn)貪心算法與活動(dòng)安排問(wèn)題

更新時(shí)間：2017年12月19日 16:51:27 作者：七度上弦丶

本篇文章主要介紹了淺談Python實(shí)現(xiàn)貪心算法與活動(dòng)安排問(wèn)題，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

貪心算法

原理：在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

特性：貪心算法采用自頂向下，以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪婪法不要回溯。能夠用貪心算法求解的問(wèn)題一般具有兩個(gè)重要特性：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

如題：給出一組活動(dòng)，告訴每個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間，要求出算出能參加的最多活動(dòng)的數(shù)量或者活動(dòng)的起止時(shí)間

貪心算法思路：

用兩個(gè)數(shù)組s，f分別存儲(chǔ)活動(dòng)的起止時(shí)間，根據(jù)活動(dòng)的結(jié)束時(shí)間對(duì)活動(dòng)進(jìn)行一個(gè)非減的活動(dòng)序列，同樣活動(dòng)的開(kāi)始時(shí)間list也要做對(duì)應(yīng)的調(diào)整，這里博主是通過(guò)冒泡排序同步交換的，舉例：活動(dòng)（1，4）（2，3）（3，5）那么我們得到的

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

通過(guò)比較下一個(gè)活動(dòng)的開(kāi)始時(shí)間與上一個(gè)活動(dòng)的結(jié)束時(shí)間的大小關(guān)系，確定這兩個(gè)活動(dòng)是否是相容的，如果開(kāi)始時(shí)間大于結(jié)束時(shí)間，則相容，反之不相容,代碼如下

#用冒泡排序?qū)Y(jié)束時(shí)間進(jìn)行排序，同時(shí)得到對(duì)應(yīng)的開(kāi)始時(shí)間的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)]
  #初始選擇第一個(gè)活動(dòng)
  j = 0
  for i in range(1,n):
    #如果下一個(gè)活動(dòng)的開(kāi)始時(shí)間大于等于上個(gè)活動(dòng)的結(jié)束時(shí)間
    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))

執(zhí)行結(jié)果如下：輸入11個(gè)活動(dòng)的起止時(shí)間，輸出相容的活動(dòng)的起止時(shí)間