怎么使用Python贪心算法

这篇文章主要介绍“怎么使用Python贪心算法”,在日常操作中,相信很多人在怎么使用Python贪心算法问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”怎么使用Python贪心算法”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

成都创新互联主营新荣网站建设的网络公司,主营网站建设方案,app开发定制,新荣h5成都小程序开发搭建,新荣网站营销推广欢迎新荣等地区企业咨询

1 找零问题

假设商店老板需要找零 n 元钱,钱币的面额有100元,50元,20元,5元,1元,如何找零使得所需钱币的数量最少?(注意:没有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 背包问题

常见的背包问题有整数背包和部分背包问题。那问题的描述大致是这样的。

一个小偷在某个商店发现有 n 个商品,第 i 个商品价值 Vi元,重 Wi  千克。他希望拿走的价值尽量高,但他的背包最多只能容纳W千克的东西。他应该拿走那些商品?

  • 0-1背包:对于一个商品,小偷要么把他完整拿走,要么留下。不能只拿走一部分,或把一个商品拿走多次(商品为金条)

  • 分数背包:对于一个商品,小偷可以拿走其中任意一部分。(商品为金砂)

对于 0-1 背包 和 分数背包,贪心算法是否都能得到最优解?为什么?

显然,贪心算法对于分数背包肯定能得到最优解,我们计算每个物品的单位重量的价值,然后将他们降序排序,接着开始拿物品,只要装得下全部的该类物品那么就可以全装进去,如果不能全部装下就装部分进去直到背包装满为止。

而对于此问题来说,显然0-1背包肯定装不满。即使偶然可以,但是也不能满足所有0-1背包问题。0-1背包(又叫整数背包问题)还可以分为两种:一种是每类物品数量都是有限的(bounded)。一种是数量无限(unbounded),也就是你想要的多少有多少,这两种都不能使用贪心策略。0-1背包是典型的第一种整数背包问题。

分数背包代码实现:

# 每个商品元组表示(价格,重量) goods = [(60, 10), (100, 20), (120, 30)] # 我们需要对商品首先进行排序,当然这里是排好序的 goods.sort(key=lambda x: x[0]/x[1], reverse=True)   # w 表示背包的容量 def fractional_backpack(goods, w):  # m 表示每个商品拿走多少个  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 拼接最大数字问题

有 n 个非负数,将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大?

例如:32, 94, 128, 1286, 6, 71 可以拼接成的最大整数为 94716321286128.

注意1:字符串比较数字大小和整数比较数字大小不一样!!!  字符串比较大小就是首先看第一位,大的就大,可是一个字符串长,一个字符串短如何比较呢?比如128和1286比较

思路如下:

# 简单的:当两个等位数相比较

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

# 当出现了下面的不等位数相比较,如何使用贪心算法呢?

# 我们转化思路,拼接字符串,比较结果

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

数字拼接代码如下:

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 活动选择问题

假设有 n 个活动,这些活动要占用同一片场地,而场地在某时刻只能供一个活动使用。

每一个活动都有一个开始时间 Si 和结束时间 Fi (题目中时间以整数表示)表示活动在 [Si, fi) 区间占用场地。(注意:左开右闭)

问:安排哪些活动能够使该场地举办的活动的个数最多?

贪心结论:最先结束的活动一定是最优解的一部分。

证明:假设 a 是所有活动中最先结束的活动,b是最优解中最先结束的活动。

如果 a=b,结论成立

如果 a!=b,则 b 的结束时间一定晚于 a 的结束时间,则此时用 a 替换掉最优解中的 b ,a  一定不与最优解中的其他活动时间重叠,因此替换后的解也是最优解。

代码如下:

# 一个元组表示一个活动,(开始时间,结束时间) activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11),  (8, 12), (2, 14), (12, 16)]   # 保证活动是按照结束时间排好序,我们可以自己先排序 activities.sort(key=lambda x:x[1])   def activity_selection(a):  # 首先a[0] 肯定是最早结束的  res = [a[0]]  for i in range(1, len(a)):  if a[i][0] >= res[-1][1]: # 当前活动的开始时间小于等于最后一个入选活动的结束时间  # 不冲突  res.append(a[i])  return res   res = activity_selection(activities) print(res)

5 最大子序和

求最大子数组之和的问题就是给定一个整数数组(数组元素有负有正),求其连续子数组之和的最大值。下面使用贪心算法逐个遍历。

代码如下:

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

到此,关于“怎么使用Python贪心算法”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!


当前题目:怎么使用Python贪心算法
地址分享:http://pwwzsj.com/article/pgpojg.html