文档章节

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

smart_w
 smart_w
发布于 2016/02/13 22:18
字数 265
阅读 150
收藏 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
粉丝 32
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

Flask框架web开发:零基础入门

Flask框架是Python开发的一个基于Werkzeug和Jinja 2的web开发微框架,它的优势就是极其简洁,但又非常灵活,而且容易学习和应用。因此Flask框架是Python新手快速开始web开发最好的选择,此外...

笔阁
6分钟前
0
0
VMware前路难测,多个厂家群雄逐鹿

在人们高谈Salesforce、亚马逊等新兴云计算厂商取得的成就时,以VMware、HPE和Cisco为代表的老牌厂商也在进行着自己的转型和变化,而且还取得一定的进展。以VMware为例,虚拟机巨头公布了第二...

linuxCool
9分钟前
0
0
什么是以太坊DAO?(一)

Decentralized Autonomous Organization,简称DAO,以太坊中重要的概念。一般翻译为去中心化的自治组织。 “在区块链上,没有人知道你是一台冰箱”——理查德布朗 到目前为止,我们列出的所有...

geek12345
11分钟前
0
0
linux防火墙操作

一、.对于centos7自带的防火墙的相关指令 #停止firewall systemctl stop firewalld.service #禁止firewall开机启动 systemctl disable firewalld.service #查看firewall的状态 systemctl st......

张锦飞
13分钟前
0
0
Linux 磁盘与磁盘分区

  Linux 系统中所有的硬件设备都是通过文件的方式来表现和使用的,我们将这些文件称为设备文件,硬盘对应的设备文件一般被称为块设备文件。本文介绍磁盘设备在 Linux 系统中的表示方法以及...

SEOwhywhy
22分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部