贪心算法
贪心算法(又称为贪婪算法 Greedy Algorithm)指的是,在对问题求解时,总是做出在当前看来是最好的选择,换句话说,就是通过一步步寻找局部最优解的方式来寻找全局最优解。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解决定全局最优解
。也就是说问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
找零问题
假设商店老板需要找零n
元钱,钱币的面额有100元,50元,20元,5元,1元,如何找零使得所需钱币的数量最少?(并没有面额10的钱币)
如果是找零276元呢?$1002+501+102+51+1*1=276$
代码如下:1
2
3
4
5
6
7
8
9
10
11# t表示商店有的零钱面额
t = [100, 50, 20, 5, 1]
# n表示n元钱
def change(t, n):
m = [0 for i in range(len(t))]
for j, money in enumerate(t):
m[j] = n // money # 除法向下取整
n = n % money # 取余
return m, n
print(change(t, 276))
背包问题
常见的背包问题有整数背包和部分背包问题。
一个小偷在某个商店发现有$n$个商品,第$i$个商品价值$V_i$元,重$W_i$千克。他希望拿走的东西价值最高,但是他的背包的容量是有限的,最多只能容纳$W$千克的东西,那么他应该拿走那些东西?0-1背包
:对于一个商品,小偷要么完整拿走,要么一点不拿,即不能拿走其中一部分,或把一个东西拿走多次。分数背包
:对于一个商品,小偷可以拿走其中的一部分。
很明显,贪心算法对于分数背包问题肯定能得到最优解,首先计算每个物品的单位重量的价值,然后将它们按照降序排列,接着开始拿取物资即可,只要装得下全部的该类商品那么就可以完全装进去;如果不能全部装下就直到背包装满为止。
对于这种问题,0-1背包
问题肯定装不满,但不排除偶然可以的情况,并不适用于所有的整数背包问题。
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# 每个商品用元组表示(价值,重量)
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
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
2==================== RESTART: C:/Users/DELL/Desktop/test.py ====================
[1, 1, 0.6666666666666666] 240.0
拼接最大数字问题
有$n$个非负数,将其按照字符串拼接的方式拼接成一个整数。如何可以使得拼接得到的整数最大?
例如:32,94, 128,1286, 6, 71可以拼接得到的最大整数位9471321286128
但字符串比较数字大小和整数比较数字大小的方式不一样,字符串比较大小就是首先看第一位,大的就大,可是一个字符长而另一个短如何比较就成了问题。
思路如下:1
2
3
4
5
6
7
8
9
10
11
12'96' a =
'97' b =
if a>b else b+a a+b
'9796'
'128' a =
'1286' b =
a+b
'1281286'
b+a
'1286128'
if a+b > b+a else b+a a+b
'1286128'
数字拼接代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18from functools import cmp_to_key
li = [30, 94, 128, 1286, 8, 71]
def xy_cmp(x, y):
# 其中1表示x>y
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), li
print(number_join(li))
输出结果如下:1
2==================== RESTART: C:/Users/DELL/Desktop/test.py ====================
94871301286128
扩充:cmp_to_key函数
该函数作用是比较1
2
3
4
5def lagestnumber(self, nums):
from functools import cmp_to_key
temp = list(map(str, nums))
temp.sort(key=cmp_to_key(lambda x, y: int(x+y) - int(y+x)), reverse=True)
return "".join(temp if temp[0] != '0' else '0')
上面这个函数有传入两个参数x,y,当x>y时返回1,等于0时返回0,否则的话返回-1,。它在list的工作原理就是将列表中的元素去两两比较,当cmp返回的是正数时交换两元素。