這篇文章主要介紹“怎么使用Python貪心算法”，在日常操作中，相信很多人在怎么使用Python貪心算法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么使用Python貪心算法”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

成都創(chuàng)新互聯(lián)主營新榮網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,app開發(fā)定制,新榮h5成都小程序開發(fā)搭建,新榮網(wǎng)站營銷推廣歡迎新榮等地區(qū)企業(yè)咨詢

1 找零問題

假設(shè)商店老板需要找零 n 元錢，錢幣的面額有100元，50元，20元，5元，1元，如何找零使得所需錢幣的數(shù)量最少?(注意：沒有10元的面額)

那要是找376元零錢呢? 100*3+50*1+20*1+5*1+1*1=375

代碼如下：

# t表示商店有的零錢的面額 t = [100, 50, 20, 5, 1]   # n 表示n元錢 def change(t, n):  m = [0 for _ in range(len(t))]  for i, money in enumerate(t):  m[i] = n // money # 除法向下取整  n = n % money # 除法取余  return m, n   print(change(t, 376)) # ([3, 1, 1, 1, 1], 0)

2 背包問題

常見的背包問題有整數(shù)背包和部分背包問題。那問題的描述大致是這樣的。

一個(gè)小偷在某個(gè)商店發(fā)現(xiàn)有 n 個(gè)商品，第 i 個(gè)商品價(jià)值 Vi元，重 Wi  千克。他希望拿走的價(jià)值盡量高，但他的背包最多只能容納W千克的東西。他應(yīng)該拿走那些商品?

• 0-1背包：對于一個(gè)商品，小偷要么把他完整拿走，要么留下。不能只拿走一部分，或把一個(gè)商品拿走多次(商品為金條)

• 分?jǐn)?shù)背包：對于一個(gè)商品，小偷可以拿走其中任意一部分。(商品為金砂)

對于 0-1 背包 和 分?jǐn)?shù)背包，貪心算法是否都能得到最優(yōu)解?為什么?

顯然，貪心算法對于分?jǐn)?shù)背包肯定能得到最優(yōu)解，我們計(jì)算每個(gè)物品的單位重量的價(jià)值，然后將他們降序排序，接著開始拿物品，只要裝得下全部的該類物品那么就可以全裝進(jìn)去，如果不能全部裝下就裝部分進(jìn)去直到背包裝滿為止。

而對于此問題來說，顯然0-1背包肯定裝不滿。即使偶然可以，但是也不能滿足所有0-1背包問題。0-1背包(又叫整數(shù)背包問題)還可以分為兩種：一種是每類物品數(shù)量都是有限的(bounded)。一種是數(shù)量無限(unbounded)，也就是你想要的多少有多少，這兩種都不能使用貪心策略。0-1背包是典型的第一種整數(shù)背包問題。

分?jǐn)?shù)背包代碼實(shí)現(xiàn)：

# 每個(gè)商品元組表示（價(jià)格，重量） goods = [(60, 10), (100, 20), (120, 30)] # 我們需要對商品首先進(jìn)行排序，當(dāng)然這里是排好序的 goods.sort(key=lambda x: x[0]/x[1], reverse=True)   # w 表示背包的容量 def fractional_backpack(goods, w):  # m 表示每個(gè)商品拿走多少個(gè)  total_v = 0  m = [0 for _ in range(len(goods))]  for i, (prize, weight) in enumerate(goods):  if w >= weight:  m[i] = 1  total_v += prize  w -= weight  # m[i] = 1 if w>= weight else weight / w  else:  m[i] = w / weight  total_v += m[i]*prize  w = 0  break  return m, total_v   res1, res2 = fractional_backpack(goods, 50) print(res1, res2) # [1, 1, 0.6666666666666666] 1.3 拼接最大數(shù)字問題

有 n 個(gè)非負(fù)數(shù)，將其按照字符串拼接的方式拼接為一個(gè)整數(shù)。如何拼接可以使得得到的整數(shù)最大?

例如：32， 94， 128， 1286， 6， 71 可以拼接成的最大整數(shù)為 94716321286128.

注意1：字符串比較數(shù)字大小和整數(shù)比較數(shù)字大小不一樣!!!  字符串比較大小就是首先看第一位，大的就大，可是一個(gè)字符串長，一個(gè)字符串短如何比較呢?比如128和1286比較

思路如下：

# 簡單的：當(dāng)兩個(gè)等位數(shù)相比較

a = '96' b = '97'   a + b if a > b else b + a

# 當(dāng)出現(xiàn)了下面的不等位數(shù)相比較，如何使用貪心算法呢?

# 我們轉(zhuǎn)化思路，拼接字符串，比較結(jié)果

 a = '128' b = '1286'  # 字符串相加 a + b = '1281286' b + a = '1286128'   a + b if a + b > b + a else b + a

數(shù)字拼接代碼如下：

from functools import cmp_to_key   li = [32, 94, 128, 1286, 6, 71]   def xy_cmp(x, y):  # 其中1表示x>y，-1,0同理  if x+y < y+x:  return 1  elif x+y > y+x:  return -1  else:  return 0   def number_join(li):  li = list(map(str, li))  li.sort(key=cmp_to_key(xy_cmp))  return "".join(li)   print(number_join(li)) # 94716321286128

4 活動(dòng)選擇問題

假設(shè)有 n 個(gè)活動(dòng)，這些活動(dòng)要占用同一片場地，而場地在某時(shí)刻只能供一個(gè)活動(dòng)使用。

每一個(gè)活動(dòng)都有一個(gè)開始時(shí)間 Si 和結(jié)束時(shí)間 Fi (題目中時(shí)間以整數(shù)表示)表示活動(dòng)在 [Si, fi) 區(qū)間占用場地。(注意：左開右閉)

問：安排哪些活動(dòng)能夠使該場地舉辦的活動(dòng)的個(gè)數(shù)最多?

貪心結(jié)論：最先結(jié)束的活動(dòng)一定是最優(yōu)解的一部分。

證明：假設(shè) a 是所有活動(dòng)中最先結(jié)束的活動(dòng)，b是最優(yōu)解中最先結(jié)束的活動(dòng)。

如果 a=b，結(jié)論成立

如果 a!=b，則 b 的結(jié)束時(shí)間一定晚于 a 的結(jié)束時(shí)間，則此時(shí)用 a 替換掉最優(yōu)解中的 b ，a  一定不與最優(yōu)解中的其他活動(dòng)時(shí)間重疊，因此替換后的解也是最優(yōu)解。

代碼如下：

# 一個(gè)元組表示一個(gè)活動(dòng)，（開始時(shí)間，結(jié)束時(shí)間） activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11),  (8, 12), (2, 14), (12, 16)]   # 保證活動(dòng)是按照結(jié)束時(shí)間排好序,我們可以自己先排序 activities.sort(key=lambda x:x[1])   def activity_selection(a):  # 首先a[0] 肯定是最早結(jié)束的  res = [a[0]]  for i in range(1, len(a)):  if a[i][0] >= res[-1][1]: # 當(dāng)前活動(dòng)的開始時(shí)間小于等于最后一個(gè)入選活動(dòng)的結(jié)束時(shí)間  # 不沖突  res.append(a[i])  return res   res = activity_selection(activities) print(res)

5 最大子序和

求最大子數(shù)組之和的問題就是給定一個(gè)整數(shù)數(shù)組(數(shù)組元素有負(fù)有正)，求其連續(xù)子數(shù)組之和的最大值。下面使用貪心算法逐個(gè)遍歷。

代碼如下：

def maxSubarray(li):  s_max, s_sum = 0, 0  for i in range(len(li)):  s_sum += li[i]  s_max = max(s_max, s_sum)  if s_sum < 0:  s_sum = 0    return s_max

到此，關(guān)于“怎么使用Python貪心算法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

網(wǎng)站標(biāo)題：怎么使用Python貪心算法
轉(zhuǎn)載源于：http://chinadenli.net/article26/pgpojg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、App開發(fā)、企業(yè)網(wǎng)站制作、商城網(wǎng)站、虛擬主機(jī)、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)