Python常用的算法——贪心算法（又称贪婪算法），你知道吗？

贪婪算法(又称贪默算法)是指，在对题目求解时，老是做出在当前看来是好的选择。也就是说，不从整体最优上加以思量，他所做出的的时在某种意义上的局部最优解。

贪婪算法并不担保会获得最优解，可是在某些题目上贪婪算法的解就是最优解。要会判定一个题目可否用贪婪算法来计较。贪婪算法和其他算法较量有明明的区别，动态筹划每次都是综合全部题目的子题目的解获适当前的最优解(全局最优解)，而不是贪婪地选择;回溯法是实行选择一条路，假如选择错了的话可以“忏悔”，也就是回过甚来从头选择其他的试试。

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 

# 当呈现了下面的不等位数对较量，怎样行使贪婪算法呢?

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!