算法进阶：贪心算法

贪心算法是一种简单而直观的算法思想，它在每一步选择中都采取在当前状态下最优的选择，以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题，即问题的最优解可以通过一系列局部最优解的选择得到。

贪心算法的基本思路是，每一步都选择当前状态下的局部最优解，并把它添加到当前解中。然后，根据已经做出的选择，对剩下的子问题进行求解。这个过程持续进行，直到得到全局最优解。

然而，贪心算法并不是适用于所有问题的。在一些情况下，贪心算法可能会得到次优解或者不正确的解。这是因为贪心算法在每一步都做出局部最优选择，并没有考虑到该选择对之后步骤的影响。

综上所述，贪心算法是一种简单而直观的算法思想，可以用来解决一些具有最优子结构的问题。

目录

贪心算法（找零问题）

背包问题

分数背包

数字拼接问题

常识：时间戳

活动选择问题

---

贪心算法（找零问题）

# 贪心算法
t = [100, 50, 20, 5, 1]
# 找零
def chang_money(n):m = [[0] for _ in range(len(t))]for i,money in enumerate(t):m[i] = n // moneyn = n % moneyreturn m,n
​
print(chang_money(376))

([3, 1, 1, 1, 1], 0)

背包问题

答：0-1背包问题不能使用贪心算法解决，

分数背包问题可以。

分数背包

先拿单位重量最值钱的物品（算法思想）

# 分数背包
# 贪心算法思想
goods = [(60,10),(100,20),(120,30)]     #(价值，重量)
​
def fenshu_bag(goods,w):goods.sort(key=lambda x:x[0]//x[1],reverse=True)        # 按照贪心算法进行拿取print(goods)m = [0 for _ in range(len(goods))]      # 记录排好价值的物品拿多少total_val = 0                           # 记录最终总价值for i,(prize,weight) in enumerate(goods):              if weight <= w:                     # 如果背包能放得下m[i] = 1total_val += prizew -= weightelse:                               # 背包放不下m[i] = w / weighttotal_val += m[i] * prizew = 0breakreturn total_val,m
print(fenshu_bag(goods,50))

[(60, 10), (100, 20), (120, 30)] (240.0, [1, 1, 0.6666666666666666])

数字拼接问题

# 数字拼接问题
from functools import cmp_to_key
​
li = [32, 94, 128, 1286, 6, 71]
​
def xy_cmp(x,y):if x+y < y+x:       # 说明y应该排在x的前面return 1elif x+y > y+x:return -1else:return 0
​
def number_join(li):li = list(map(str,li))li.sort(key=cmp_to_key(xy_cmp))     # 类似于冒泡 比较的是unicode编码return "".join(li)
​
print(number_join(li))

94716321286128

常识：时间戳

时间戳（Timestamp）是一种表示某个特定时刻的数字标识，它记录了从一个特定起始时间点到指定时刻所经过的秒数（或者毫秒数、微秒数 ，具体精度因系统和应用而异）。常见的时间戳有以下两种类型：

• Unix 时间戳：Unix 系统广泛使用的时间表示方法，它以 1970 年 1 月 1 日 00:00:00 UTC（协调世界时）作为起始时间点，记录到指定时刻历经的秒数 。例如，Unix 时间戳为 1690579200 对应的北京时间是 2023 年 7 月 29 日 00:00:00，因为从 1970 年 1 月 1 日 00:00:00 UTC 到这个时刻，恰好经过了 1690579200 秒。在 Python 中，可以使用time模块来获取和处理 Unix 时间戳：

import time
​
# 获取当前Unix时间戳
current_timestamp = time.time()  
print(current_timestamp)

活动选择问题

# 活动选择问题
activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
activities.sort(key=lambda x:x[1])      # 按照结束时间升序排列
​
def activities_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(activities_selection(activities))

[(1, 4), (5, 7), (8, 11), (12, 16)]