python常用算法(6)——贪心算法,欧几里得算法

lixiaotao 2019-10-28

1,贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的的时在某种意义上的局部最优解。

贪心算法并不保证会得到最优解,但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。贪心算法和其他算法比较有明显的区别,动态规划每次都是综合所有问题的子问题的解得到当前的最优解(全局最优解),而不是贪心地选择;回溯法是尝试选择一条路,如果选择错了的话可以“反悔”,也就是回过头来重新选择其他的试试。

1.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)

1.2  背包问题

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

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

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

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

举例:

python常用算法(6)——贪心算法,欧几里得算法

  对于 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

1.4  活动选择问题

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

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

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

python常用算法(6)——贪心算法,欧几里得算法

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

证明:假设 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)

1.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

2,欧几里得算法——最大公约数

2.1,最大公约数的定义

约数:如果整数 a 能被整数 b 整除,那么 a 叫做 b 的倍数,b 叫做 a 的约数。

最大公约数(Greatest  Common  Divisor):给定两个整数 a, b,两个数的所有公共约数中的最大值即为最大公约数。

例如:12和16的最大公约数是 4 。

2.2,欧几里得算法如下:

欧几里得算法又称为辗转相除法,用于计算两个正整数a,b的最大公约数。

  • E:设两个正整数a, b,且已知a>b
  • E1:令r = a%b(‘%‘代表取余)
  • E2:若r=0(即n整除m),结束运算,n即为结果
  • E3:否则令a=b,b=r,并返回步骤E1

欧几里得算法运用了这样一个等价式(设 gcd(a, b)代表 a 和 b 的最大公约数,mod()代表取余运算或模运算)则:

 gcd(a,  b) =  gcd(b, a mod b ) = gcd(b, a%b)

也就是说 m , n 的最大公约数等于他们相除余数(r)和 n 的最大公约数。  

例如:gcd(60, 21) = gcd(21, 18) = gcd(18, 3) = gcd(3, 0) = 3

意思就是 60对21取余18,同理21对18余3,18对3取余0,所以3为两个数的最大公约数。

2.3,证明欧几里得公式

我们的证明分为两步。第一步,证明gcd(a, b)是b, a%b 的一个公约数。第二步,证明这个公约数是最大的。

1,证明gcd(a, b)是b, a%b 的一个公约数

1,因为任意两个正整数都有最大公因数,设为 d。

2,将 a , b 分别用最大公因数 d 来表示为 a = k1*d  b = k2*d (k1,k2是两个常数)

3,设 a = k*b + c (也就是a 除以 b 商 k 余 c),然后把a = k1*d  b = k2*d  两个式子中的 a,b代入式子,得到:

c = a - k*b = k1*d - k * k2 * d,然后再提取公因数 d,得到 c = (k1 - k2 * k)*d,这就说明,c也就是 a%b有 d 这个约数,因为开始我们设 任意两个数都有最大公约数d,所以 gcd(a, b) 是 b, a%b 的一个公约数。

4,由此可以得到 c 是最大公因数 d 的倍数,得证:gcd(a, b) = gcd(b, a mod b)。所以以此类推,可以将 m n中较大的数用较小的数的余数 r 替换,实现了降维,所以有了E3的步骤。 

2,证明我们求出来的公约数是最大的

1,数学是一门严谨的学科,我们需要严谨的正面,我们知道 c(a%b) =  k1*d - k * k2 * d    b = k2*d,所以我们只需要证明k1-k*k2, k2互质即可。

2,这里可以用到反证法,我们假设 k1 - k*k2 = q*t  k2=p*t,再讲这个k1 代入最开始的 a=k1*d ,得到 a=(q*t + k*k2)*d,再利用乘法分配律得到: a = q*t*d + k*k2*d,这时候我们发现,k2*d就是b,将其代入,得到 a=q*t*d + b*d

3,我们在将k2 = p*t代入开始的b = k2*d,得到b = p*t*d,再把这个式子代到a = q*t*d+b*d.得到了:a = q*t*d+p*t*d.提取公因数:a=(q+p)*t*d

4,再和b=p*t*d比较,发现他们的最大公因数变成了t*d和开始矛盾,所以假设不成立,反证成功!

2.4,如何计算最大公约数?

1,欧几里得:辗转相除法(欧几里得算法)

2,《九章算术》:更相减损术

   代码如下:

# 递归法:保证a>b
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 递推法
def gcd1(a, b):
    if a < b:
        a, b = b, a
    while b > 0:
        r = a % b
        a = b
        b = r
    return a

因为这是一个伪递归,所以时间复杂度不高。

2.5,应用:实现分数计算

   利用欧几里得算法实现一个分数类,支持分数的四则运算。

   代码如下:

# _*_coding:utf-8_*_

class Fraction:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        x = self.gcd(a, b)
        self.a /= x
        self.b /= x

    # 最大公约数
    def gcd(self, a, b):
        while b > 0:
            r = a % b
            a = b
            b = r
        return a

    # 最小公倍数
    def zgs(self, a, b):
        # 12 16 -> 4
        # 3 * 4 * 4=48
        x = self.gcd(a, b)
        return (a * b / x)

    # 加法的内置方法
    def __add__(self, other):
        # 1/12 + 1/20
        a = self.a
        b = self.b
        c = other.a
        d = other.b
        fenmu = self.zgs(b, d)
        femzi = a * (fenmu / b) + c * (fenmu / d)
        return Fraction(femzi, fenmu)

    def __str__(self):
        return "%d/%d" % (self.a, self.b)


f = Fraction(30, 16)
print(f)

 2.7 欧几里得算法的缺点

   欧几里得算法是计算两个数最大公约数的传统算法,无论从理论还是实际效率上都是很好地。但是却有一个致命的缺陷,这个缺陷在素数比较小的时候一般是感受不到的,只有在大素数时才会显现出来。

一般实际应用中的整数很少会超过64位(当然现在已经允许128位),对于这样的整数,计算两个数之间的模很简单。对于字长为32位的平台,计算两个不超过32位的整数的模,只需要一个指令周期,而计算64位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过64位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多CPU时间。对于现代密码算法,要求计算128位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模。

由J. Stein 1961年提出的Stein算法很好的解决了欧几里德算法中的这个缺陷,Stein算法只有整数的移位和加减法,为了说明Stein算法的正确性,首先必须注意到以下结论:

  gcd(a,a)=a,也就是一个数和其自身的公约数仍是其自身。
  gcd(ka,kb)=k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换。特殊地,当k=2时,说明两个偶数的最大公约数必然能被2整除。
  当k与b互为质数,gcd(ka,b)=gcd(a,b),也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地,当k=2时,说明计算一个偶数和一个奇数的最大公约数时,可以先将偶数除以2。

   代码如下:

def gcd_Stein(a, b):  
    if a < b:
        a, b = b, a
    if (0 == b):
        return a
    if a % 2 == 0 and b % 2 == 0:
        return 2 * gcd_Stein(a/2, b/2)
    if a % 2 == 0:
        return gcd_Stein(a / 2, b)
    if b % 2 == 0:
        return gcd_Stein(a, b / 2)
    
    return gcd_Stein((a + b) / 2, (a - b) / 2)

参考文献:https://www.cnblogs.com/jason2003/p/9797750.html

https://www.cnblogs.com/Dragon5/p/6401596.html

相关推荐