文档章节

动态规划之硬币表示问题

一贱书生
 一贱书生
发布于 2016/11/22 10:17
字数 2563
阅读 2
收藏 1
点赞 0
评论 0

问题描述:

  有数量不限的硬币,币值为25分、10分、5分和1分,请编写代码计算n分有几种表示法。

求解思路:

  这也是典型的动态规划问题,我们可以这样考虑:当只有1分的硬币时,n从1到n分别有多少种表示方法;当有1分和5分的硬币时,n从1到n分别有多少种表示方法,因此类推,直到我们将1分、5分、10分和25分的硬币全部使用完。思想类似于0-1背包问题,0-1背包问题的具体求解方法可以参考我的上一篇博客动态规划之0-1背包问题。我们用数组coins[i]={1,5,10,25}表示各种币值,此时可以维护一张二维表ways[i][j],其中横坐标表示前i种表示币值,j表示硬币的总值,则ways[i][j]表示能用前i种硬币来表示j分的方法数。

 当增加一种新的硬币币值时,有两种情况:

(1)不加入此种币值:ways[i][j]=ways[i-1][j];

(2)加入此种币值:加入该枚硬币之前的方法数为ways[i][j-coins[i]],那么加入该枚硬币之后构成j分的方法数也为ways[i][j-coins[i]]。

 因此当增加一种新的币值时,j分的表示方法数为ways[i][j]=ways[i-1][j]+ways[i][j-coins[i]]。

代码实现

[java] view plain copy

 

  1. import java.util.Scanner;  
  2. public class Main {  
  3.     public static void main(String[] args) {  
  4.         Scanner sc = new Scanner(System.in);  
  5.         int n = sc.nextInt();  
  6.         int[] coins = {1, 5, 10, 25};  
  7.         int[][] ways = new int[4][n + 1];  
  8.         for (int i = 0; i < 4; i++)  
  9.             ways[i][0] = 1; //第0行初始化为1  
  10.         for (int j = 1; j <= n; j++)  
  11.             ways[0][j] = 1; //第0列初始化为1  
  12.         for (int i = 1; i < 4; i++) {  
  13.             for (int j = 1; j <= n; j++) {  
  14.                 if (j >= coins[i])  
  15.                     ways[i][j] = ways[i - 1][j] + ways[i][j - coins[i]];  
  16.                 else  
  17.                     ways[i][j] = ways[i - 1][j];  
  18.             }  
  19.         }  
  20.         System.out.println(ways[3][n]);  
  21.     }  
  22. }  

当然,维护二维表未免过于复杂,我们可以维护一张一维表,即用一维数组ways[j]来记录j分的表示方法数。改进的代码实现如下:

[java] view plain copy

 

  1. import java.util.Scanner;  
  2. public class Main {  
  3.     public static void main(String[] args) {  
  4.         Scanner sc=new Scanner(System.in);  
  5.         int n=sc.nextInt();  
  6.         int []coins={1,5,10,25};  
  7.         int []ways=new int[n+1];  
  8.         ways[0]=1;  
  9.         for(int i=0;i<4;i++){  
  10.             for(int j=coins[i];j<=n;j++){  
  11.                 ways[j]=ways[j]+ways[j-coins[i]];  
  12.             }  
  13.         }  
  14.         System.out.println(ways[n]);  
  15.     }  
  16. }

 

问题:要找K元的零钱,零钱的种类已知,保存在数组coins[]中,要求:求出构成K所需的最少硬币的数量和零钱的具体数值。
分析:(1)贪心算法:,先从面额最大的硬币开始尝试,一直往下找,知道硬币总和为N。但是贪心算法不能保证能够找出解(例如,给,2,3,5,然后N=11,导致无解5,5,1)。
(2)动态规划:
思想:快速实现递归(将前面计算的结果保存在数据里,后面重复用的时候直接调用就行,减少重复运算)
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合 于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如 果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题 的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。
代码:

/*找零钱问题:要找 K元的零钱,零钱的种类有 coins[],要求零钱的张数最少,用 road[]来找出具体使用的零钱*/
public class MinCount_coins {
    public static void main (String[] args) { 
       int coins[]={3,5};
       int k=4;
       int road[]=new int[k+1];
       int min=getMinCount(k ,coins ,road );
       if(min>Integer. MAX_VALUE-k ){ //min 没有另外赋值,则表示零钱不够
        System.out. println( "零钱不够!" );
       }else{
        System.out. println( "数值为" +k +" 时,需要的最少的硬币数为: "+ min);
           for(int j=k;j>0;){
            System.out. print( road[ j]+ "\t");
            j=j-road[j];  //j为当前要找的零钱值, road[j]为当前面额下,最近加入的零钱
           }
       }
    } 

    public static int getMinCount (int k,int c[],int r[]){
     int a[]=new int[k+1];//保存最近加入的零钱值
     a [0]=0;
     for(int x=1;x<k+1;x++){ //要求a[k],先求a[1]~a[k-1]
         if(x>=c[0]){  //给a[x]附初值
             a[x]=a[x-c[0]]+1;
             r[x]=c[0];
         }else{   //要找零钱比最小零钱值还小,零钱不够
             a[x]=Integer.MAX_VALUE- k;
         }
         for(int i=1;i<c.length;i++){
             if(x>=c[i]&&(a[x]>a[x-c[i]]+1)){//x-c[i]表示当前值减去coins[]中值,即可由前面那些子问题+1一次得来
                  a[ x]= a[ x- c[ i]]+1;
                  r[ x]= c[ i];
             }
         }
     }
     return a[k];
    }
}

 

本文中的解解法综合考虑了各种情况,比如改变了零钱的种类,零钱不够等情况

 

 

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

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

硬币找零问题描述:现存在一堆面值为 V1、V2、V3 … 个单位的硬币,问最少需要多少个硬币才能找出总值为 T 个单位的零钱?假设这一堆面值分别为 1、2、5、21、25 元,需要找出总值 T 为 63 元的零钱。

很明显,只要拿出 3 个 21 元的硬币就凑够了 63 元了。

基于上述动态规划的思想,我们可以从 1 元开始计算出最少需要几个硬币,然后再求 2 元、3元…每一次求得的结果都保存在一个数组中,以后需要用到时则直接取出即可。那么我们什么时候需要这些子问题的解呢?如何体现出由子问题的解得到较大问题的解呢?

其实,在我们从 1 元开始依次找零时,可以尝试一下当前要找零的面值(这里指 1 元)是否能够被分解成另一个已求解的面值的找零需要的硬币个数再加上这一堆硬币中的某个面值之和,如果这样分解之后最终的硬币数是最少的,那么问题就得到答案了。

单是上面的文字描述太抽象,先假定以下变量:

values[] : 保存每一种硬币的币值的数组
valueKinds :币值不同的硬币种类数量,即values[]数组的大小

money : 需要找零的面值
coinsUsed[] : 保存面值为 i 的纸币找零所需的最小硬币数

算法描述:

当求解总面值为 i 的找零最少硬币数 coinsUsed[ i ] 时,将其分解成求解 coinsUsed[ i – cents]和一个面值为 cents 元的硬币,由于 i – cents < i , 其解 coinsUsed[ i – cents] 已经存在,如果面值为 cents 的硬币满足题意,那么最终解 coinsUsed[ i ] 则等于 coinsUsed[ i – cents] 再加上 1(即面值为 cents)的这一个硬币。

下面用代码实现并测试一下:

 
  1. public class CoinsChange {  
  2.     /**  
  3.      * 硬币找零:动态规划算法  
  4.      *   
  5.      * @param values  
  6.      *            :保存每一种硬币的币值的数组  
  7.      * @param valueKinds  
  8.      *            :币值不同的硬币种类数量,即coinValue[]数组的大小  
  9.      * @param money  
  10.      *            :需要找零的面值  
  11.      * @param coinsUsed  
  12.      *            :保存面值为i的纸币找零所需的最小硬币数  
  13.      */ 
  14.     public static void makeChange(int[] values, int valueKinds, int money,  
  15.             int[] coinsUsed) {  
 
    • coinsUsed[0] = 0;  
    •         // 对每一分钱都找零,即保存子问题的解以备用,即填表  
    •         for (int cents = 1; cents <= money; cents++) {  
    •  
    •             // 当用最小币值的硬币找零时,所需硬币数量最多  
    •             int minCoins = cents;  
    •  
    •             // 遍历每一种面值的硬币,看是否可作为找零的其中之一  
    •             for (int kind = 0; kind < valueKinds; kind++) {               
    •                 // 若当前面值的硬币小于当前的cents则分解问题并查表  
    •                 if (values[kind] <= cents) {  
    •                     int temp = coinsUsed[cents - values[kind]] + 1;  
    •                     if (temp < minCoins) {  
    •                         minCoins = temp;  
    •                     }  
    •                 }  
    •             }  
    •             // 保存最小硬币数  
    •             coinsUsed[cents] = minCoins;  
    •  
    •             System.out.println("面值为 " + (cents) + " 的最小硬币数 : " 
    •                     + coinsUsed[cents]);  
    •         }  
    •     }  
    •       
    •     public static void main(String[] args) {  
    •  
    •         // 硬币面值预先已经按降序排列  
    •         int[] coinValue = new int[] { 25211051 };  
    •         // 需要找零的面值  
    •         int money = 63;  
    •  
    •  // 保存每一个面值找零所需的最小硬币数,0号单元舍弃不用,所以要多加1  
    •         int[] coinsUsed = new int[money + 1];  
    •  
    •         makeChange(coinValue, coinValue.length, money, coinsUsed);  
    •     }  
    • 测试结果:

      面值为 1 的最小硬币数 : 1
      面值为 2 的最小硬币数 : 2
      面值为 3 的最小硬币数 : 3
      面值为 4 的最小硬币数 : 4
      面值为 5 的最小硬币数 : 1
      面值为 6 的最小硬币数 : 2
      ...
      ...
      面值为 60 的最小硬币数 : 3
      面值为 61 的最小硬币数 : 4
      面值为 62 的最小硬币数 : 4
      面值为 63 的最小硬币数 : 3

       上面的代码并没有给出具体应该是哪几个面值的硬币,这个可以再使用一些数组保存而打印出来。

/**
 * 功能:给定数量不限的硬币,币值为25分,10分,5分,1分,计算n分有几种表示法。

 */

 

 

[java] view plain copy

 

  1. public static int makeChange(int n){  
  2.     return makeChange(n,25);  
  3. }  
  4.   
  5. /** 
  6.  * 递归的终止条件:完全简化为1分。 
  7.  * @param n 
  8.  * @param denom 
  9.  * @return 
  10.  */  
  11. public static int makeChange(int n,int denom){  
  12.     int next_denom=0;  
  13.     switch(denom){  
  14.     case 25:  
  15.         next_denom=10;  
  16.         break;  
  17.     case 10:  
  18.         next_denom=5;  
  19.         break;  
  20.     case 5:  
  21.         next_denom=1;  
  22.         break;  
  23.     case 1:  
  24.         return 1;  
  25.     }  
  26.       
  27.     int ways=0;  
  28.     for(int i=0;i*denom<=n;i++){  
  29.         ways+=makeChange(n-i*denom,next_denom);  
  30.     }  
  31.     return ways;  
 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
动态规划算法思想解决找零钱问题

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

niaonao ⋅ 2017/10/16 ⋅ 0

动态规划

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

廖少少 ⋅ 2017/09/27 ⋅ 0

动态规划入门之硬币问题

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度, 因此它比回溯法、暴力法等要快许多。动态规...

SVD ⋅ 2016/09/13 ⋅ 0

详解动态规划最少硬币找零问题--JavaScript实现

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

YinTokey ⋅ 05/27 ⋅ 0

动态规划(Dynamic Programming)算法与LC实例的理解

动态规划(Dynamic Programming)算法与LC实例的理解 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法...

qq_32690999 ⋅ 05/10 ⋅ 0

贪心算法精讲

一.贪心算法的基本概念 当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它。但有时会有更简单有效的算法。我们来看一个找硬币的例子。假设有四种硬币,它们的面值分别为二角五...

凡平 ⋅ 2011/10/09 ⋅ 0

小朋友学算法(8):贪心算法与动态规划算法

一、贪心算法 例1:假设有1,5,11这三种面值的硬币,给定一个数,比如28,最少使用的硬币组合是什么? 分析:碰到这种问题,咱们很自然会想起先用最大的面值,再用次大的面值……这样得到的...

翡翠森林Z ⋅ 01/23 ⋅ 0

面试题解| coins in a line iii 区间DP

专栏 | 九章算法 网址 | http://www.jiuzhang.com 题 coins in a line iii 区间DP 题目描述 有 n 个硬币排成一条线,每一枚硬币有不同的价值。两个参赛者轮流从任意一边取一枚硬币,直到没有硬...

九章算法 ⋅ 06/12 ⋅ 0

分治策略

分治策略 本文包括 分治的基本概念 二分查找 快速排序 归并排序 找出伪币 棋盘覆盖 最大子数组 源码链接:https://github.com/edisonleolhl/DataStructure-Algorithm/tree/master/Divede-an...

廖少少 ⋅ 2017/09/14 ⋅ 0

几种常用的算法简介

1、穷举法 穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出满足条件的解。 穷举法的运用关键在于解决两个问题: 如何列举所有的可能解; 如何判别可能解...

hanzhankang ⋅ 2014/01/21 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

mysql in action / alter table

change character set ALTER SCHEMA `employees` DEFAULT CHARACTER SET utf8mb4 DEFAULT COLLATE utf8mb4_general_ci ;ALTER TABLE `employees`.`t2` CHARACTER SET = utf8mb4 , COLLAT......

qwfys ⋅ 今天 ⋅ 0

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

MySQL

查看表相关命令 - 查看表结构    desc 表名- 查看生成表的SQL    show create table 表名- 查看索引    show index from  表名 使用索引和不使用索引 由于索引是专门用于加...

stars永恒 ⋅ 昨天 ⋅ 0

easyui学习笔记

EasyUI常用控件禁用方法 combobox $("#id").combobox({ disabled: true }); ----- $("#id").combobox({ disabled: false}); validatebox $("#id").attr("readonly", true); ----- $("#id").r......

miaojiangmin ⋅ 昨天 ⋅ 0

金山WPS发布了Linux WPS Office

导读 近日,金山WPS发布了Linux WPS Office中文社区版新版本,支持大部分主流Linux系统,功能更加完善,兼容性、稳定性大幅度提升。本次更新WPS将首次在Linux提供专业办公文件云存储服务,实...

问题终结者 ⋅ 昨天 ⋅ 0

springboot2输出metrics到influxdb

序 本文主要研究一下如何将springboot2的metrics输出到influxdb maven <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-bo......

go4it ⋅ 昨天 ⋅ 0

微信小程序 - 选择图片显示操作菜单

之前我分享过选择图片这个文章,但是我在实际开发测试使用中发现一个问题在使用 wx.chooseImage 选择照片显示出第一格是拍照,后面是相册里的图片。这种实现之前说过了,效果如下。 但是你从...

hello_hp ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部