重庆做网站代运营,域名什么意思,佛山h5建站模板,app推广软件有哪些贪心算法是一种简单而直观的算法思想#xff0c;它在每一步选择中都采取在当前状态下最优的选择#xff0c;以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题#xff0c;即问题的最优解可以通过一系列局部最优解的选择得到。
贪心算法的基本思路是它在每一步选择中都采取在当前状态下最优的选择以期望最终得到全局最优解。贪心算法通常适用于一些具有最优子结构的问题即问题的最优解可以通过一系列局部最优解的选择得到。
贪心算法的基本思路是每一步都选择当前状态下的局部最优解并把它添加到当前解中。然后根据已经做出的选择对剩下的子问题进行求解。这个过程持续进行直到得到全局最优解。
然而贪心算法并不是适用于所有问题的。在一些情况下贪心算法可能会得到次优解或者不正确的解。这是因为贪心算法在每一步都做出局部最优选择并没有考虑到该选择对之后步骤的影响。
综上所述贪心算法是一种简单而直观的算法思想可以用来解决一些具有最优子结构的问题。
目录
贪心算法找零问题
背包问题
分数背包
数字拼接问题
常识时间戳
活动选择问题 贪心算法找零问题 # 贪心算法
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(keylambda x:x[0]//x[1],reverseTrue) # 按照贪心算法进行拿取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 xy yx: # 说明y应该排在x的前面return 1elif xy yx:return -1else:return 0
def number_join(li):li list(map(str,li))li.sort(keycmp_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(keylambda 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)]
