文档章节

硬币包含问题(最少找钱问题)

smart_w
 smart_w
发布于 2016/02/13 22:18
字数 238
阅读 130
收藏 1
点赞 1
评论 0

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

package main

import (
	"fmt"
	"sort"
)

func coin_change(arr []int, total int) int {
	sort.Ints(arr)
	tmp := total
	length := len(arr)
	var amount int = 0

	for i := length - 1; i >= 0; i-- {
		if tmp%arr[i] == 0 {
			amount += tmp / arr[i]
			return amount
		} else if tmp >= arr[0] {
			amount += tmp / arr[i]
			tmp = tmp % arr[i]
		} else {
			amount = 0
			tmp = total
		}
	}

	return -1
}

func main() {
	arr := []int{1, 2, 5}
	amount :=11
	fmt.Printf("need coin num:%d\n", coin_change(arr, amount))
}

//输出结果-------------------------------------------------
//arr := []int{1, 2, 5} amount:=11 输出:need coin num:3
//arr := []int{1, 2}  amount:=11 输出:need coin num:6
//arr := []int{2, 5}  amount:=11 输出:need coin num:-1
//arr := []int{2} amount:=3 输出:need coin num:-1


© 著作权归作者所有

共有 人打赏支持
smart_w
粉丝 30
博文 71
码字总数 19544
作品 0
武汉
程序员
动态规划算法思想解决找零钱问题

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

niaonao ⋅ 2017/10/16 ⋅ 0

详解动态规划最少硬币找零问题--JavaScript实现

硬币找零问题是动态规划的一个经典问题,其中最少硬币找零是一个变种,本篇将参照上一篇01背包问题的解题思路,来详细讲解一下最少硬币找零问题。如果你需要查看上一篇,可以点击下面链接: ...

YinTokey ⋅ 05/27 ⋅ 0

动态规划

动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列(LIS) 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最...

廖少少 ⋅ 2017/09/27 ⋅ 0

投币自动售票程序

题目:投币自动售票程序 要求: 找钱原则“有大面值的货币就不找小面试的货币” 例如:当售票机中有10c=>1, 20c=>3, 50c=>1。需要找60c,这个时候就要找1个50c的和1个10c的硬币,而不是3个20c...

技术小胖子 ⋅ 2017/11/04 ⋅ 0

动态规划之硬币表示问题

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

一贱书生 ⋅ 2016/11/22 ⋅ 0

一道算法题:在超市用现金结账时,如何付钱以及收银员如何找钱才能使钱的张数最少?

一道算法题:在超市用现金结账时,有以下几种纸币,arr[] =[100,50,20,5,1] ,现在求我如何付钱以及收银员如何找钱,才能使付给收银员张数和收银员找回的张数加起来最少?比如我结账需付19,...

努力的C ⋅ 2017/10/20 ⋅ 0

动态规划入门之硬币问题

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度, 因此它比回溯法、暴力法等要快许多。动态规...

SVD ⋅ 2016/09/13 ⋅ 0

动态规划(Dynamic Programming)算法与LC实例的理解

动态规划(Dynamic Programming)算法与LC实例的理解 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法...

qq_32690999 ⋅ 05/10 ⋅ 0

小朋友学算法(8):贪心算法与动态规划算法

一、贪心算法 例1:假设有1,5,11这三种面值的硬币,给定一个数,比如28,最少使用的硬币组合是什么? 分析:碰到这种问题,咱们很自然会想起先用最大的面值,再用次大的面值……这样得到的...

翡翠森林Z ⋅ 01/23 ⋅ 0

贪心算法精讲

一.贪心算法的基本概念 当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它。但有时会有更简单有效的算法。我们来看一个找硬币的例子。假设有四种硬币,它们的面值分别为二角五...

凡平 ⋅ 2011/10/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vue-cli是什么?

vue-cli是什么? vue-cli 是vue.js的脚手架,用于自动生成vue.js+webpack的项目模板,分为vue init webpack-simple 项目名 和vue init webpack 项目名 两种。 当然首先你的安装vue,webpack...

韦姣敏 ⋅ 24分钟前 ⋅ 0

12c rman中输入sql命令

12c之前版本,要在rman中执行sql语句,必须使用sql "alter system switch logfile"; 而在12c版本中,可以支持大量的sql语句了: 比如: C:\Users\zhengquan>rman target / 恢复管理器: Release 1...

tututu_jiang ⋅ 30分钟前 ⋅ 0

java 线程池

概述 减少了创建和销毁线程的次数,每个工作线程都可以被重复利用,可执行多个任务 可以根据系统的承受能力,调整线程池中工作线线程的数目,防止因为因为消耗过多的内存,而把服务器累趴下(...

轨迹_ ⋅ 35分钟前 ⋅ 0

Nginx的https配置记录以及http强制跳转到https的方法梳理

Nginx的https配置记录以及http强制跳转到https的方法梳理 一、Nginx安装(略) 安装的时候需要注意加上 --with-httpsslmodule,因为httpsslmodule不属于Nginx的基本模块。 Nginx安装方法: ...

Yomut ⋅ 47分钟前 ⋅ 0

SpringCloud Feign 传递复杂参数对象需要注意的地方

1.传递复杂参数对象需要用Post,另外需要注意,Feign不支持使用GetMapping 和PostMapping @RequestMapping(value="user/save",method=RequestMethod.POST) 2.在传递的过程中,复杂对象使用...

@林文龙 ⋅ 49分钟前 ⋅ 0

如何显示 word 左侧目录大纲

打开word说明文档,如下图,我们发现左侧根本就没有目录,给我们带来很大的阅读障碍 2 在word文档的头部菜单栏中,切换到”视图“选项卡 3 然后勾选“导航窗格”选项 4 我们会惊奇的发现左侧...

二营长意大利炮 ⋅ 52分钟前 ⋅ 0

智能合约编程语言Solidity之线上开发工具

工具地址:https://ethereum.github.io/browser-solidity/ 实例实验: 1.创建hello.sol文件 2.调试输出结果

硅谷课堂 ⋅ 53分钟前 ⋅ 0

ffmpeg 视频格式转换

转 Mp4 格式 #> ffmpeg -i input.avi -c:v libx264 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 -s 1......

Contac ⋅ 今天 ⋅ 0

VCS仿真生成vpd文件(verilog)

VCS仿真生成vpd文件(verilog): https://www.cnblogs.com/OneFri/p/5987673.html SYNOPSYS VCS常用命令使用详解 https://blog.csdn.net/hemmingway/article/details/49382551 DVE是synopsys公......

whoisliang ⋅ 今天 ⋅ 0

Spring Boot启动配置原理

几个重要的事件回调机制 配置在META-INF/spring.factories ApplicationContextInitializer SpringApplicationRunListener 只需要放在ioc容器中 ApplicationRunner CommandLineRunner 启动流程......

小致dad ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部