Java动态规划之硬币找零问题实现代码

动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后在求解较大子问题的时候需要用到这些子问题的解，就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式，例如保存在数组中。

用一个实际例子来体现动态规划的算法思想——硬币找零问题。

问题描述:

假设有几种硬币，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。例如几种硬币为[1, 3, 5], 面值2的最少硬币数为2(1, 1), 面值4的最少硬币数为2(1, 3), 面值11的最少硬币数为3(5, 5, 1或者5, 3, 3).

问题分析:

假设不同的几组硬币为数组coin[0, ..., n-1]. 则求面值k的最少硬币数count(k), 那么count函数和硬币数组coin满足这样一个条件:

count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
并且在符合条件k - coin[i] >= 0 && k - coin[i] < k的情况下, 前面的公式才成立.
因为k - coin[i] < k的缘故, 那么在求count(k)时, 必须满足count(i)(i <- [0, k-1])已知, 所以这里又涉及到回溯的问题.

所以我们可以创建一个矩阵matrix[k + 1][coin.length + 1], 使matrix[0][j]全部初始化为0值, 而在matrix[i][coin.length]保存面值为i的最少硬币数.

而且具体的过程如下:

* k|coin 1  3  5  min
  * 0    0  0  0  0
  * 1    1  0  0  1
  * 2    2  0  0  2
  * 3    3  1  0  3, 1
  * 4    2  2  0  2, 2
  * 5    3  3  1  3, 3, 1
  * 6    2  2  2  2, 2, 2
  * ...

最后, 具体的Java代码实现如下:

public static int backTrackingCoin(int[] coins, int k) {//回溯法+动态规划
    if (coins == null || coins.length == 0 || k < 1) {
      return 0;
    }
    int[][] matrix = new int[k + 1][coins.length + 1];
    for (int i = 1; i <= k; i++) {
      for (int j = 0; j < coins.length; j++) {
        int preK = i - coins[j];
        if (preK > -1) {//只有在不小于0时, preK才能存在于数组matrix中, 才能够进行回溯.
          matrix[i][j] = matrix[preK][coins.length] + 1;//面值i在进行回溯
          if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {//如果当前的硬币数目是最少的, 更新min列的最少硬币数目
            matrix[i][coins.length] = matrix[i][j];
          }
        }
      }
    }
    return matrix[k][coins.length];
  }

代码经过测试, 题目给出的测试用例全部通过!

总结

以上就是本文关于Java动态规划之硬币找零问题实现代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题。如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

您可能感兴趣的文章:

  • Java实现的猴子吃桃问题算法示例
  • Java实现分解任意输入数的质因数算法示例
  • Java求10到100000之间的水仙花数算法示例
  • java实现的各种排序算法代码示例
  • 多模字符串匹配算法原理及Java实现代码
  • 70行Java代码实现深度神经网络算法分享
  • Java编程实现基于用户的协同过滤推荐算法代码示例
赞 (0)

相关推荐

  • Java实现分解任意输入数的质因数算法示例

    Java实现分解任意输入数的质因数算法示例

    本文实例讲述了Java实现分解任意输入数的质因数算法.分享给大家供大家参考,具体如下: 分解任意输入数的质因数: 质因数概念:任何一个合数都可以写成几个质数相乘的形式.其中每个质数都是这个合数的因数,叫做这个合数的分解质因数.分解质因数只针对合数. 例如:12 = 2x2x3  18 = 2 x 3 x 3等等 下面来讲解一下这个算法的思路:第一:我们首先写一个求素数的函数:第二;我们做一个分解质因数的函数,然后在其中引入素数函数来判断是否为素数: 下面给出代码(仅供参考): package j

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

  • Java编程实现基于用户的协同过滤推荐算法代码示例

    协同过滤简单来说是利用某兴趣相投.拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要. 协同过滤又可分为评比(rating)或者群体过滤(social filtering)协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热 UserCF的核心思想即为根据用户数据模拟向量相似度,我们根据这个相似度,来找出指定用户的相似用户,然后将相似用

  • Java求10到100000之间的水仙花数算法示例

    Java求10到100000之间的水仙花数算法示例

    本文实例讲述了Java求10到100000之间的水仙花数算法.分享给大家供大家参考,具体如下: 水仙花数: 概念:水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身.(例如:1^3 + 5^3+ 3^3 = 153) 算法思路分析:这个算法我们分两个步骤来进行:第一:我们做一个求一个数的位数的函数:第二:我们通过调用此函数来进行10到100000之间素数的计算! 下面给出具体的代码(仅供参考): package javastudy; public class

  • 70行Java代码实现深度神经网络算法分享

    70行Java代码实现深度神经网络算法分享

    对于现在流行的深度学习,保持学习精神是必要的--程序员尤其是架构师永远都要对核心技术和关键算法保持关注和敏感,必要时要动手写一写掌握下来,先不用关心什么时候用到--用不用是政治问题,会不会写是技术问题,就像军人不关心打不打的问题,而要关心如何打赢的问题. 程序员如何学习机器学习 对程序员来说,机器学习是有一定门槛的(这个门槛也是其核心竞争力),相信很多人在学习机器学习时都会为满是数学公式的英文论文而头疼,甚至可能知难而退.但实际上机器学习算法落地程序并不难写,下面是70行代码实现的反向多层(BP

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • Java动态规划之硬币找零问题实现代码

    动态规划的基本思想是将待求解问题分解成若干个子问题,先求解子问题,并将这些子问题的解保存起来,如果以后在求解较大子问题的时候需要用到这些子问题的解,就可以直接取出这些已经计算过的解而免去重复运算.保存子问题的解可以使用填表方式,例如保存在数组中. 用一个实际例子来体现动态规划的算法思想--硬币找零问题. 问题描述: 假设有几种硬币,并且数量无限.请找出能够组成某个数目的找零所使用最少的硬币数.例如几种硬币为[1, 3, 5], 面值2的最少硬币数为2(1, 1), 面值4的最少硬币数为2(1,

  • Java动态规划之硬币找零问题实现示例

    目录 问题描述: 问题分析: 具体的过程如下: 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法.20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的

  • java动态规划算法——硬币找零问题实例分析

    本文实例讲述了java动态规划算法--硬币找零问题.分享给大家供大家参考,具体如下: 问题描述 现在有3种硬币分别为:1元,5元,10元,现在给你63元,让你全部换成硬币,求出最小硬币数量,也就是说,怎么用最少的硬币数凑成63元. 分析问题 解决这个问题,我们可以将这个大问题分成若干个小问题,自下而上解决问题. 1元对应的最小硬币数是1 2元对应的最小硬币数是2 3元对应的最小硬币数是3 4元对应的最小硬币数是4 -- 63元对应的最小硬币数是XXX 假设我们将前边计算出的金额对应的最小硬币数像

  • js贪心算法 钱币找零问题代码实例

    js贪心算法 钱币找零问题代码实例

    给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量. 例如,美国硬币面额有1.5.10.25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分.1个10美分和1个10美分共三个硬币.这个算法要解决的就是诸如此类的问题.我们来看看如何用动态规划的方式来解决. 对于每一种面额,我们都分别计算所需要的硬币数量.具体算法如下: 如果全部用1美分的硬币,一共需要36个硬币 如果用5美分的硬币,则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币 如果用10美

  • Python基于回溯法子集树模板解决找零问题示例

    Python基于回溯法子集树模板解决找零问题示例

    本文实例讲述了Python基于回溯法子集树模板解决找零问题.分享给大家供大家参考,具体如下: 问题 有面额10元.5元.2元.1元的硬币,数量分别为3个.5个.7个.12个.现在需要给顾客找零16元,要求硬币的个数最少,应该如何找零?或者指出该问题无解. 分析 元素--状态空间分析大法:四种面额的硬币看作4个元素,对应的数目看作各自的状态空间,遍历状态空间,其它的事情交给剪枝函数. 解的长度固定:4 解的编码:(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4

  • JS使用贪心算法解决找零问题示例

    本文实例讲述了JS使用贪心算法解决找零问题.分享给大家供大家参考,具体如下: 前面介绍了JS贪心算法解决背包问题,这里再来看看找零问题的解决方法. 在现实生活中,经常遇到找零问题,假设有数目不限的面值为20,10,5,1的硬币. 给出需要找零数,求出找零方案,要求:使用数目最少的硬币. 对于此类问题,贪心算法采取的方式是找钱时,总是选取可供找钱的硬币的最大值.比如,需要找钱数为25时,找钱方式为20+5,而不是10+10+5. 贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很

  • Java动态规划之丑数问题实例讲解

    Java动态规划之丑数问题实例讲解

    问题描述: 我们把只包含质因子 2.3 和 5 的数称作丑数(Ugly Number).求按从小到大的顺序的第 n 个丑数. 注: 1也是丑数 思路: 我们来分析一下丑数如何得到,肯定是由前面的丑数乘2,乘3或者乘5得到,因此这是一道动态规划题. 使用 dp[i] 记录第i个丑数, 初始值dp[0] = 1,返回 dp[n-1] 使用 a,b,c 记录以及 2,3,5 分别乘到了第几个丑数 动态规划方程为: dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3),

  • Java使用正则表达式实现找出数字功能示例

    本文实例讲述了Java使用正则表达式实现找出数字功能.分享给大家供大家参考,具体如下: 1.问题: String str = "fjd789klsd908434jk#$$%%^38488545",从中找出78990843438488545,请找到解决办法 2.实现代码: /** * */ package com.you.model; /** * @author YouHaidong * */ public class FindNumber { /** * 字符串str */ publi

  • JS实现的找零张数最小问题示例

    JS实现的找零张数最小问题示例

    本文实例讲述了JS实现的找零张数最小问题.分享给大家供大家参考,具体如下: 完整代码如下: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>www.jb51.net 找零问题</title> </head> <body> <script> var price = pro

  • Java动态规划之编辑距离问题示例代码

    Java动态规划之编辑距离问题示例代码

    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,

随机推荐