Python贪心算法实例小结
作者:wangbowj123 发布时间:2021-08-05 21:10:17
标签:Python,贪心算法
本文实例讲述了Python贪心算法。分享给大家供大家参考,具体如下:
1. 找零钱问题:假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1元的硬币。在超市结账 时,如果 需要找零钱, 收银员希望将最少的硬币数找给顾客。那么,给定 需要找的零钱数目,如何求得最少的硬币数呢?
# -*- coding:utf-8 -*-
def main():
d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币面值
d_num = [] # 存储每种硬币的数量
s = 0
# 拥有的零钱总和
temp = raw_input('请输入每种零钱的数量:')
d_num0 = temp.split(" ")
for i in range(0, len(d_num0)):
d_num.append(int(d_num0[i]))
s += d[i] * d_num[i] # 计算出收银员拥有多少钱
sum = float(raw_input("请输入需要找的零钱:"))
if sum > s:
# 当输入的总金额比收银员的总金额多时,无法进行找零
print("数据有错")
return 0
s = s - sum
# 要想用的钱币数量最少,那么需要利用所有面值大的钱币,因此从数组的面值大的元素开始遍历
i = 6
while i >= 0:
if sum >= d[i]:
n = int(sum / d[i])
if n >= d_num[i]:
n = d_num[i] # 更新n
sum -= n * d[i] # 贪心的关键步骤,令sum动态的改变,
print("用了%d个%f元硬币"%(n, d[i]))
i -= 1
if __name__ == "__main__":
main()
2. 求最大子数组之和问题:给定一个整数数组(数组元素有负有正),求其连续子数组之和的最大值。
# -*- coding:utf-8 -*-
def main():
s = [12,-4,32,-36,12,6,-6]
print("定义的数组为:",s)
s_max, s_sum = 0, 0
for i in range(len(s)):
s_sum += s[i]
if s_sum >= s_max:
s_max = s_sum # 不断更新迭代s_max的值,尽可能的令其最大
elif s_sum < 0:
s_sum = 0
print("最大子数组和为:",s_max)
if __name__ == "__main__":
main()
3. 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。 对于给定的n(n <= 5000)和k(k <= 1000)个加油站位置,编程计算最少加油次数。
# 设汽车加满油后可行驶n公里,且旅途中有k个加油站
def greedy():
n = 100
k = 5
d = [50,80,39,60,40,32]
# 表示加油站之间的距离
num = 0
# 表示加油次数
for i in range(k):
if d[i] > n:
print('no solution')
# 如果距离中得到任何一个数值大于n 则无法计算
return
i, s = 0, 0
# 利用s进行迭代
while i <= k:
s += d[i]
if s >= n:
# 当局部和大于n时则局部和更新为当前距离
s = d[i]
# 贪心意在令每一次加满油之后跑尽可能多的距离
num += 1
i += 1
print(num)
if __name__ == '__main__':
greedy()
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/wangbowj123/article/details/78335203
0
投稿
猜你喜欢
- 本文主要介绍我在利用Django写文章时,采用的注册方法。首先说一下整体逻辑思路:•处理用户注册数据,•产生token,生成验证URL,•发
- 本文整理了3种鼠标经过图片,图片边框加粗或改变颜色的方法,希望大家喜欢。下面3中只是提供了一个方法,具体的鼠标经过图片的样式,你自己可以修改
- 需求描述我们需要登录考勤系统(网页端,非手机端)进行签到,如果不想每天都早早起来打卡签到,就可以通过写程序实现这一功能。业务梳理通过长时间的
- 什么是Firebug从事了数年的Web开发工作,越来越觉得现在对WEB开发有了更高的要求。要写出漂亮的HTML代码;要编写精致的CSS样式表
- 需求:(1) 获取你对象chrome前一天的浏览记录中的所有网址(url)和访问时间,并存在一个txt文件中(2)将这个txt文件发送给指定
- 本文实例讲述了python简单程序读取串口信息的方法。分享给大家供大家参考。具体分析如下:这段代码需要调用serial模块,通过while循
- 我们的网络协议一般是把数据转换成JSON之后再传输。之前在Java里面,实现序列化和反序列化,不管是 jackson ,还是 fastjso
- 局部变量什么是局部变量通俗定义:函数内部定义的变量就叫局部变量。话不多说,代码如下:def test1(): a = 300 # 定义一个局
- isNaN函数 返回一个 Boolean 值,指明提供的值是否是保留值 NaN (不是数字)。 NaN 即 Not a Number isN
- 题目描述1266. 访问所有点的最小时间 - 力扣(LeetCode)平面上有 n 个点,点的位置用整数坐标表示 poi
- 这篇文章主要介绍了Python scrapy增量爬取实例及实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学
- 起因:有一批数据需要每个月进行分析,数据存储在excel中,行标题一致,需要横向合并进行分析。数据示意:具有多个代码:# -*- codin
- 本文主要分析的是web.py库的application.py这个模块中的代码。总的来说,这个模块主要实现了WSGI兼容的接口,以便应用程序能
- 1 如何在网页中获取 JSON 数据?打开一个具有动态渲染的网页,按 F12 打开浏览器开发工具,点击“网络&r
- ASP日期和时间函数我们经常会用到,本文列出了12个常用的asp日期和时间函数的语法及用法以作备忘!1.Now Now() 取
- 前言:Python中for循环和while循环本质上是没有区别的,但是在实际应用上,针对性不太一样。for循环,主要应用在遍历中,体现的是遍
- '==' 比较的是两个对象的值'is' 比较的是两个对象的内存地址(id)下面我们着重理解 'is&
- 当我们建立一个数据库时,并且想将分散在各处的不同类型的数据库分类汇总在这个新建的数据库中时,尤其是在进行数据检验、净化和转换时,将会面临很大
- 我们经常遇到各种字典套字典的数据,例如:nest_dict = { 'a': 1, 'b
- SQL Server的作业调度来建立自动备份的方法◆1、进入企业管理器中->管理->sql server代理->作业;◆2