文档章节

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

smart_w
 smart_w
发布于 2016/02/13 22:18
字数 265
阅读 137
收藏 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
js算法初窥05(算法模式02-动态规划与贪心算法)

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

zaking
05/29
0
0
动态规划之硬币表示问题

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

一贱书生
2016/11/22
2
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring加载properties文件的两种方式

在项目中如果有些参数经常需要修改,或者后期可能需要修改,那我们最好把这些参数放到properties文件中,源代码中读取properties里面的配置,这样后期只需要改动properties文件即可,不需要修...

架构师springboot
10分钟前
0
0
分布式事务,原来可以这么玩?

多个数据要同时操作,如何保证数据的完整性,以及一致性? 答 : 事务 ,是常见的做法。 举个栗子: 用户下了一个订单,需要修改 余额表 , 订单 表 , 流水 表 ,于是会有类似的伪代码: st...

微笑向暖wx
13分钟前
0
0
IE6兼容PNG32图片显示PNG8图片

IE6并不是不支持PNG图片,只是不支持半透明通道。 是支持PNG8色表引索全透明的。 以往都是通过滤镜或统统使用PNG8实现兼容。 但是我发现twitter的png图标可以在chrome中显示png32,在IE6显示...

linsk1998
25分钟前
0
0
linux运维需要掌握的基础知识

踏入linux运维工程师这一职业,其实有很多工具技能需要掌握,下面我来给大家一一介绍。 1、shell脚本和另一个脚本语言,shell是运维人员必须具备的,不懂这个连入职都不行,至少也要写出一些...

linuxprobe16
26分钟前
0
0
《netty入门与实战》笔记-03:数据传输载体 ByteBuf 介绍

ByteBuf结构 首先,我们先来了解一下 ByteBuf 的结构 以上就是一个 ByteBuf 的结构图,从上面这幅图可以看到: ByteBuf 是一个字节容器,容器里面的的数据分为三个部分,第一个部分是已经丢弃...

Funcy1122
59分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部