python 贪心算法的实现
作者:Achilles_Heel 发布时间:2023-01-25 08:18:50
贪心算法
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
基本思路
思想
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止 。
步骤
遍历初始集合X中的备选元素
利用贪心策略在X中确定一个元素,并将其加入到可行解S中
得到可行解S
P即为贪心策略,用来选择符合条件的元素。
例子——硬币找零
假设某国硬币面值有1,5,10,25,100元五种面额,若店员为顾客找零时,需要给顾客找零a=36元,求硬币数最少的情况。
这里我们的贪心策略为:
先找到最接近a的值,然后对a进行更新,然后进行循环。
代码实现
def shortNum(a):
coins = [1,5,10,25,100]
out = []
coins = coins[::-1]
for i in coins:
num = a//i
out=out+[i,]*num
a = a-num*i
if a<=0:
break
return out
a = 36
print(shortNum(a))
例子——任务规划
问题描述:
输入为任务集合X= [r1,r2,r3,...,rn],每个任务ri,都对应着一个起始时间ai与结束时间bi
要求输出为最多的相容的任务集。
如上图,r1与r2相容,r3与r1和r2都不相容。
那么这里的贪心策略我们可以设为:
先将结束时间最短的任务加入到S中,
再从剩下的任务的任务中选择结束时间最短的,且判断与S集合中的任务是否相容
若不相容,则换下一个时间最短的任务,并进行比较
循环,直至X为空。
代码实现
# 任务规划
from collections import OrderedDict
task = OrderedDict()
task['r1'] = [0,4]
task['r2'] = [5,8]
task['r3'] = [10,13]
task['r4'] = [15,18]
task['r5'] = [7,11]
task['r6'] = [2,6]
task['r7'] = [2,6]
task['r8'] = [2,6]
task['r9'] = [12,16]
task['r10'] = [12,16]
task['r11'] = [12,16]
task['r12'] = [0,3]
listTask = list(task.items())
# 根据bi进行排序,结束时间早的在前面(冒泡排序)
for i in range(len(listTask)-1):
for j in range(len(listTask)-i-1):
if listTask[j][1][1] > listTask[j+1][1][1]:
listTask[j],listTask[j+1]=listTask[j+1],listTask[j]
print(listTask)
out = []
out.append(listTask.pop(0))
def isValid(temp,out):
for k in range(len(out)):
if temp[1][0]<out[k][1][1]:
# 相交
return False
return True
for j in range(len(listTask)):
temp = listTask.pop(0)
# 判断是否相交
# 相交则continue
# 不相交则out.append(temp)
for k in range(len(out)):
if isValid(temp,out):
out.append(temp)
# else:continue 语句可以不写
else:
continue
print(out)
来源:https://www.cnblogs.com/sunny0824/p/13466341.html
猜你喜欢
- 如果你取相对路径不是在主文件里,可能就会有相对路径问题:"No such file or directory"。因为 p
- 本文实例讲述了C语言实现访问及查询MySQL数据库的方法。分享给大家供大家参考,具体如下:1、添加头文件路径(MySQL安装路径中的incl
- 转自: http://www.qqread.com/mysql/z442108305.html对于程序开发人员而言,目前使用最流行的两种后台
- 目前python 提供了几种多线程实现方式 thread,threading,multithreading ,其中thread模块比较底层,
- 初试牛刀假设你希望学习Python这门语言,却苦于找不到一个简短而全面的入门教程。那么本教程将花费十分钟的时间带你走入Python的大门。本
- 不管学习什么编程语言一开始都会经历的四步开发工具安装IDE安装设置 依赖/包 国内镜像项目构建工具,管理依赖/包一、Golang 开发工具安
- 谷歌驱动下载地址:http://chromedriver.storage.googleapis.com/index.html一、seleni
- 当我们开始精通编程语言时,我们不仅希望实现最终目标,而且希望使我们的程序高效。在这个教程中,我们将学习一些Ipython的命令,这些命令可以
- 前言:终于来了一篇有质量的文章,我个人感觉非常不错,《jfinal与bootstrap之间的登录跳转实战》。具体内容包含有点击登录弹出模态框
- 简介在php中,类型的继承使用extends关键字,而且最多只能继承一个父类,php不支持多继承。class MyClass {
- 在日常的测试工作中,我们的测试用例一般都是保存在Excel文件中,当然也有一些公司会使用Xmind来编写测试用例,那么为什么我们在这里只是讲
- 前言最近碰到了照片识别的场景,正好使用了face_recognition项目,给大家分享分享。face_recognition项目能做的很多
- new 和 make 是 Go 语言中用于内存分配的原语。简单来说,new 只分配内存,make 用于初始化 slice、map 和 cha
- 本文实例讲述了JavaScript数据结构中串的表示与应用。分享给大家供大家参考,具体如下:类似于线性表的顺序存储结构,用一组地址连续的存储
- 1)忘记在 if , elif , else , for , while , class ,def 声明末尾添加 :(导致 “SyntaxE
- 这篇文章主要介绍了用python写测试数据文件过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- pytorch构建双模型第一部分:构建"se_resnet152","DPN92()"双模型impo
- 为了确保字符串按预期显示,我们可以使用 format() 方法对结果进行格式化。字符串 format()format() 方法允许您格式化字
- 本文实例讲述了javascript自动生成包含数字与字符的随机字符串的方法。分享给大家供大家参考。具体如下:这里主要用到Math.rando
- 【1】 以XML 返回 (1)未定义属性的 select logisticsId,logisticsName from LogisticsC