文档章节

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

smart_w
 smart_w
发布于 2016/02/13 22:18
字数 265
阅读 130
收藏 1

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 = 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
粉丝 31
博文 74
码字总数 23007
作品 0
武汉
程序员
动态规划算法思想解决找零钱问题

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

niaonao
2017/10/16
0
0
详解动态规划最少硬币找零问题--JavaScript实现

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

YinTokey
05/27
0
0
动态规划

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

廖少少
2017/09/27
0
0
投币自动售票程序

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

技术小胖子
2017/11/04
0
0
js算法初窥05(算法模式02-动态规划与贪心算法)

  在前面的文章中(js算法初窥02(排序算法02-归并、快速以及堆排)我们学习了如何用分治法来实现归并排序,那么动态规划跟分治法有点类似,但是分治法是把问题分解成互相独立的子问题,最...

zaking
05/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Zookeeper总结

Zookeeper的部分概念 什么是zookeeeper? Zookeeper是一个分布式服务的协调中心 zookeeper节点的角色类型? Leader(领导者)、Follower(跟随者)、Observer(观察者) Leader 负责更新系统...

DemonsI
18分钟前
0
0
Redis学习笔记

常用命令 从Docker进入Redis的命令 sudo docker exec -it redis /bin/bash

OSC_fly
18分钟前
0
0
SqlServer查询某个日期的数据

select * from View_ZJMONITORINGCORROSION where ENTERDATE > CONVERT(datetime,DATEADD(day,1,'2017/12/28 14:53:07'))...

笑丶笑
20分钟前
0
0
常用编码规范

Standard characters https://ascii.cl/

yeahlife
21分钟前
0
0
flannel实战

docker swarm mode的出现是个里程碑,官方原生的编排调度看起来都成雏形了,但是swarm mode和容器外部系统的对接、网络性能始终不尽人意,swarm mode下各种开源周边不能使用,感觉swarm mod...

China_OS
23分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部