贪心算法

贪心算法（又称为贪婪算法 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
>>> a = '96'
>>> b = '97'
>>> a+b if a>b else b+a
'9796'
>>> a = '128'
>>> b ='1286'
>>> a+b
'1281286'
>>> b+a
'1286128'
>>> a+b if a+b > b+a else b+a
'1286128'

数字拼接代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from 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
5
def 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返回的是正数时交换两元素。