文档章节

动态规划--找零钱

o
 osc_g8254g7s
发布于 2019/08/19 18:04
字数 284
阅读 7
收藏 0
def

精选30+云产品,助力企业轻松上云!>>>

 1 coins=[1,2,5,10,50,100] #硬币面值
 2 
 3 def cal_change(total):
 4     if total<=0:
 5         return 0
 6     else:
 7         res=[]
 8         for coin in [x for x in coins if x<=total]:
 9             num=1+cal_change(total-coin)
10             res.append(num)
11         return min(res)
12     
13 if __name__=='__main__':
14     for i in range(20,31):
15         print('{0}:{1} coins at least.'.format(i,cal_change(i)))

结果:

20:2 coins at least.
21:3 coins at least.
22:3 coins at least.
23:4 coins at least.
24:4 coins at least.
25:3 coins at least.
26:4 coins at least.
27:4 coins at least.
28:5 coins at least.
29:5 coins at least.
30:3 coins at least.

效率测试:

1 if __name__=='__main__':
2     import time
3     start=time.time()
4     print(cal_change(33))    
5     end=time.time()
6     print('time collapsed:{0} seconds'.format(end-start))

输出:

5
time collapsed: 27.66892910003662 seconds

 

高效改进版:使用字典记住已经算出来的结果。

import time
coins=[1,2,5,10,50,100] #硬币面值

cache=dict() #字典缓存,记住运算结果
def cal_change(total):
    if total in cache.keys():
        return cache[total]
    if total<=0:
        return 0
    else:
        res=[]
        for coin in [x for x in coins if x>=total:
            if total>=coin:
                num=1+cal_change(total-coin)
                res.append(num)
        cache[total]=min(res)
        return cache[total]

if __name__=='__main__':
    start=time.time()
    print(cal_change(33))    
    end=time.time()
    print('time collapsed:{0} seconds'.format(end-start))

输出:

5
time collapsed: 0.00035190582275390625 seconds

 

参考:https://www.cnblogs.com/jiayongji/p/7118895.html

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Python算法之零钱兑换问题的解法

零钱兑换问题求解 我们平时出去购买商品,在商店支付的时候,如果要找零的话,都不希望营业员找回一堆零钱,存放非常的不方便。特别是在自动售卖机上购买商品的时候,我们发现现在的自动售卖...

hongliang888
05/18
7
0
动态规划算法思想解决找零钱问题

动态规划算法思想解决找零钱问题 前言 关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受...

niaonao
2017/10/16
0
0
找零钱的两种方法

有时候,去便利店买几块钱的东西,但没有零钱,只能给他们一张100的,他们可能找给我一沓10块的和几枚硬币。我不喜欢这么多的零钱,要知道,钱越零散,散失地就越快,我希望找给我的零钱张数...

一个程序员的自省
2011/03/06
0
0
动态规划之硬币表示问题

问题描述: 有数量不限的硬币,币值为25分、10分、5分和1分,请编写代码计算n分有几种表示法。 求解思路: 这也是典型的动态规划问题,我们可以这样考虑:当只有1分的硬币时,n从1到n分别有多...

一贱书生
2016/11/22
138
0
后台开发 3个题目 array_chunk, 100块钱找零钱(动态规划 dynamic programming), 双向循环链表 llist 删除节点

arraychunk 实现 http://php.net/manual/en/function.array-chunk.php <?phpfunction myarraychunk($a, $sz) {$b = [];if ($sz < 1) { return null;}for ($i = 0, $n = count($a); $i < $n;......

osc_6x8y8c2x
2018/07/30
4
0

没有更多内容

加载失败,请刷新页面

加载更多

百度技术沙龙第67期 百度开源专场

本文作者:HelloDeveloper 具体的产品案例,分享百度开源技术最新实践经验。目前这些项目都已经在 github/baidu 上开源。 什么是 PaddlePaddle 深度学习平台? 首先做个简单的介绍,PaddleP...

百度开发者中心
2019/07/23
11
0
Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 01:15 US Supreme Court deems half of Oklahoma a Native American Reservation - (reuters.com) 美国最高法院认为俄克拉荷马州的一半是印第安人保留地 得分:131 | 评...

FalconChen
今天
26
0
OSChina 周五乱弹 —— 求求你吃了我吧,不要再玩弄食物的感情了

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @巴拉迪维 :张喆的单曲《陷阱 》 这首歌已经在网易找不到原唱了,不知道被哪家买了版权。#今日歌曲推荐# 《陷阱 》- 张喆 手机党少年们想听歌...

小小编辑
今天
32
1
清华陈文光教授:AI 超算基准测试的最新探索和实践。

道翰天琼认知智能平台为您揭秘新一代人工智能。 无规矩不成方圆。放在超级计算机的研发领域,没有一个大家普遍接受的算力评测指标,便难以推动超算迅猛发展。 而现在伴随着人工智能的发展,大...

jackli2020
今天
7
0
@RequestMapping, consumes 提交简单有意思的测试

getParm @GetMapping("getParm")public Result getParm(String id){ System.out.println(); return ResultFactory.success(id);} 等同于 == bodyParm @PostMapping("bodyParm......

莫库什勒
今天
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部