时间戳

首页 > 技术文章 > 贪心算法

贪心算法

harryblog 2019-04-16 10:26 原文

一 什么是贪心算法

贪心算法(又称贪婪算法)是指在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑他所做出的是某种意义上的局部优解
贪心算法并不保证会得到最优解, 但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算

贪心算法每一步必须满足一下条件：

  • 可行的：即它必须满足问题的约束。
  • 局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
  • 不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

二 找零问题

假设商店老板需要找零n元钱， 钱币的面额有：100元 50元 20元 5元 1元，如何找零使得所需钱币的数量最少？

解决思路：

  • 先用n去整除每张钱币的面额，得到的结果为每张钱币的数量
  • 再用n对钱币取模并将结果赋值给n

实现代码

t = [100, 50, 20, 5, 1]  # 钱的面额

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

 三 背包问题

一个小偷在某个商店发现n个商品，第i个商品价值Vi元，重量Wi千克。它希望拿走的价值尽量高，但是他的背部最多能容纳W千克的东西，他应该拿走哪些商品?
0-1背包：对于一个商品，小偷要么把它完整拿走,要么留下。不能只拿走一部分，或把一个商品拿走多次。（商品为金条）
分数背包： 对于一个商品，小偷可以拿走其中任意一部分(商品为金砂)

举例：

商品1：V1=60 W1=10
商品2：V2=100 W2=20
商品3：V3=120 W3=30
背包容量：W=50
对于0-1背包和分数背包，贪心算法是否能得到最优解？为什么？

 

分数背包实现：

goods = [(60, 10), (100, 20), (120, 30)]  # 每个元素表示(价格,重量)
goods.sort(key=lambda x: x[0] / x[1], reverse=True)  # 安商品价值排序 倒序

def fractional_backpack(goods, w):
    m = [0 for _ in range(len(goods))]
    total_v = 0
    for i, (price, weight) in enumerate(goods):
        if w >= weight:
            m[i] = 1
            w -= weight
            total_v += price  # 总价值
        else:
            m[i] = w / weight
            w = 0
            total_v += m[i] * price
            break
    return total_v, m


print(fractional_backpack(goods, 50))

四 拼接最大数字问题

有n个非负整数, 将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大？
例如：32,94,128,1286,6,71 可以拼接的最大整数位94716321286128

from functools import cmp_to_key
li = [32, 94, 128, 1286, 6, 71]

def xy_cmp(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)


print(number_join(li))

 使用冒泡排序后拼接实现的代码

li = [32, 94, 128, 1286, 6, 71]

def number_join(li):
    li = list(map(lambda x: str(x), li))
    for i in range(0, len(li) - 1):
        for j in range(0, len(li) - 1 - i):
            if li[j] + li[j + 1] < li[j + 1] + li[j]:
                li[j], li[j + 1] = li[j + 1], li[j]
        print(li)

    return "".join(li)


print(number_join(li))

五  活动选择问题

假设有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):
    res = [a[0]]
    for i in range(1, len(a)):
        if a[i][0] >= res[-1][1]:  # 当前活动的开始时间要小于等于最后一个入选活动的结束时间
            # 不冲突
            res.append(a[i])
    return res
print(activity_selection(activities))

 

推荐阅读