贪心算法是一种简单而直观的算法思想，它在每一步选择中都采取在当前状态下最优的选择，以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题，即问题的最优解可以通过一系列局部最优解的选择得到。
贪心算法的基本思路是，每一步都选择当前状态下的局部最优解，并把它添加到当前解中。然后，根据已经做出的选择，对剩下的子问题进行求解。这个过程持续进行，直到得到全局最优解。
然而，贪心算法并不是适用于所有问题的。在一些情况下，贪心算法可能会得到次优解或者不正确的解。这是因为贪心算法在每一步都做出局部最优选择，并没有考虑到该选择对之后步骤的影响。
综上所述，贪心算法是一种简单而直观的算法思想，可以用来解决一些具有最优子结构的问题。
目录
贪心算法（找零问题）
背包问题
分数背包
数字拼接问题
常识：时间戳
活动选择问题
贪心算法（找零问题）
# 贪心算法
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 // money
n = n % money
return 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] = 1
total_val += prize
w -= weight
else: # 背包放不下
m[i] = w / weight
total_val += m[i] * prize
w = 0
break
return 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 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)) # 类似于冒泡 比较的是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)]
