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

目录
  • 问题描述:
  • 问题分析:
  • 具体的过程如下:

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。

动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。举例:线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;背包问题:01背包问题,完全背包问题,多重背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

文章主要介绍了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 硬币找零内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

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

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

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

  • 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动态规划之丑数问题实例讲解

    问题描述: 我们把只包含质因子 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),

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

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

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

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

随机推荐