java最少需要多少张纸币_最少钱币数(凑硬币)详解-2-动态规划算法(初窥)-编程练习题(100)...

本文主要是介绍java最少需要多少张纸币_最少钱币数(凑硬币)详解-2-动态规划算法(初窥)-编程练习题(100)...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

这篇使用动态规划算法来解决这个问题,借这篇博客初窥动态规划算法。最少钱币数问题也可以看作多重背包问题。

那么什么是动态规划算法?

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

———From Baidupedia

那么我们如何去描述它?

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

概念讲完,开始做题。

题目:

最少钱币数

问题描述

这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了 6 种钱币面值为 2、5、10、20、50、100,用来凑 15 元,可以用 5 个 2 元、1个 5 元,或者 3 个 5 元,或者 1 个 5 元、1个 10 元,等等。显然,最少需要 2 个钱币才能凑成 15 元。

你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。

输入形式

输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值 M(1 <= M<= 2000,整数),接着的一行中,第一个整数 K(1 <= K <= 10)表示币种个数,随后是 K个互不相同的钱币面值 Ki(1 <= Ki <= 1000)。输入 M=0 时结束。

输出形式

每个测试用例输出一行,即凑成钱数值 M 最少需要的钱币个数。如果凑钱失败,输出“Impossible”。你可以假设,每种待凑钱币的数量是无限多的。

样例输入

15

6 2 5 10 20 50 100

1

1 2

0

样例输出

2

Impossible

分析:

上一篇最少钱币数-1-贪心算法(错,或者叫有问题)-CCF-CSP练习题中使用的贪心算法解决的凑硬币问题,有些情况下是可以得出正解的,比如后一个钱币面值没有达到前一个钱币面值的2倍时;但对于某些情况来说得出的解是错误的。比如有3种面值分别为3元,5元,7元的纸币,(1)那么至少用几张纸币能凑够10元?我的直觉告诉我先选面值最大的,7元一张,然后再选面值5元的时候发现超额了(7+5>10),因此我们选3元一张,最少用2张纸币就能凑够10元,这个时候可以得出正解。这个方法容易想出来,抽象一点可以叫贪心算法(每次都选当前看来最好的选择,不从整体最优考虑),(2)那么至少用几张纸币能凑够8元呢?如果还按照贪心算法来解的话会得到Impossible。因为先选一张7元,然后再选5元(7+5>8)不行,换选3元(7+3>8)还不行。但是仔细看会发现5元+3元不是8元吗,怎么会无解。所以贪心算法解这个问题是不行的。考CSP时只能用来骗点分。

到这里我们发现用贪心算法会出现两个问题 1)本来有解用贪心法算出来却无解,例如上例(2)至少用几张纸币能凑够8元?;2)算出来的解不是最优解,例如有 1元,7元,9元,10元四种面值的纸币,要凑18元 ,贪心算法会给出答案需要3张(10元1张,7元1张,1元1张),但是我们可以明显看出 2张(两张9元)才是答案。

那么问题出在了哪里?在这里用贪心算法是有条件的——后一个的权值(这里就是纸币面值)是前一个的2倍或以上才可以使用,这里10不到9的两倍。贪心算法不是对所有问题都能得到整体最优解。关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。在这里我们先选择了10元,在第二步的时候9元就选择不了了(10+9>18了),选择10元这个状态影响到选9元这个状态,所以会错过9+9这个最优解。所以说贪心算法在对问题求解时,总是做出在当前看来是最好的选择,不从整体最优考虑。

这里说了这么多,都是在讨论上一篇,本篇主要讨论正确解法——动态规划算法解题。可能你已经不耐烦了,那么先上一个此问题递推公式(也可以叫做动态转移方程):(注:v[i]表示可以使用的纸币的面额组成的数组,dp[m]表示要凑m元至少需要多少张纸币。)

dp[m] = min(dp[m-v[i] ]+1,dp[m])

那么这个方程怎么得来的呢?我们先了解一下DP(Dynamic Programing)的基本原理:首先,找到某个状态的最优解,然后在它的帮助下,找到下一个状态的最优解。不明白这个概念没关系,我们以上面的例子为例来分析一下——如果我们有4种面值分别为1元,3元,5元,7元的纸币,那么至少需要几张纸币就能凑出8元?

在分析这个问题之前先来思考一个问题,至少用多少张纸币能凑够m(表示money)元(m<8)呢?为什么要这么问呢? 动态规划的思想:(1)当我们遇到一个大问题时,总是习惯把问题的规模变小,这样便于分析讨论。 (2)这个规模变小后的问题和原来的问题是同质的,除了规模变小,其它的都是一样的, 本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

现在让我们从规模最小的m开始。当m=0时,即我们需要多少个币来凑够0元呢? 由于1,3,5,7都大于0,即没有比0小的币值,因此凑够0元我们最少需要0个币。 (em......Interesting,这个分析很傻是不是?别着急,这个思路有利于我们理清动态规划究竟在做些什么。) 为了方便我们用dp[m]=c来表示凑够m元最少需要c个硬币。于是我们就得到了dp[0]=0, 表示凑够0元最小需要0个硬币。当m=1时,只有面值为1元的硬币可用, 因此我们拿起一个面值为1的硬币,接下来只需要凑够0元即可,而这个是已经知道的dp[0]=0。所以,dp[1]=dp[1-1]+1=dp[0]+1=0+1=1。当m=2时, 仍然只有面值为1的硬币可用,于是我拿起一个面值为1的硬币, 接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量),而这个答案也已经知道了。 所以dp[2]=dp[2-1]+1=dp[1]+1=1+1=2。分析到这里,聪明的你可能已经看出端倪,没看出来没关系,接下来让我们看看m=3时的情况。当m=3时我们能用的硬币就有两种了:1元的和3元的( 5元的仍然没用,因为你需要凑的数目是3元,5元面值太大了)。 既然能用的硬币有两种,我就有两种方案。如果我拿了一个1元的硬币,我的目标就变为了: 凑够3-1=2元需要的最少硬币数量。即dp[3]=dp[3-1]+1=dp[2]+1=2+1=3。 这个方案说的是,我拿3个1元的硬币;第二种方案是我拿起一个3元的硬币, 我的目标就变成:凑够3-3=0元需要的最少张纸币。即dp[3]=dp[3-3]+1=dp[0]+1=0+1=1. 这个方案说的是,我拿1个3元的硬币。好了,这两种方案哪种更优呢? 记得我们的问题是要用最少的硬币数量来凑够3元。所以, 选择dp[3]=1,怎么来的呢?具体是这样得到的:dp[3]=min(dp[3-1]+1, dp[3-3]+1)。

有了上面的分析,这回应该能看出个门道了吧,你可能早已按奈不住了,现在我们就可以从以上分析抽象出我们想要的东西了——递推公式。从以上的文字中, 我们要抽出动态规划里非常重要的两个概念:状态和状态转移方程。

上文中dp[m]表示凑够m元需要的最少硬币数量,我们将它定义为该问题的"状态", 这个状态是怎么找出来的呢?是根据子问题定义状态。你找到子问题,状态也就浮出水面了。 最终我们要求解的问题,可以用这个状态来表示:dp[8],即凑够8元最少需要多少个硬币。 那状态转移方程是什么呢?既然我们用dp[m]表示状态,那么状态转移方程自然包含dp[m], 上文中包含状态 dp[m] 的方程是:dp[3]=min(dp[3-1]+1, dp[3-3]+1)。没错, 它就是状态转移方程,描述状态之间是如何转移的。当然,我们要对它抽象一下,dp[m] = min(dp[ m-v[i] ]+1,dp[m]),其中 m-v[i] >=0,v[i] 表示第i个硬币的面值,方程的含义是拿出一个面值为 v[i] 的硬币后,凑够 m-v[i] 元至少需要的硬币数目(dp[m-v[i] ])+1和凑够m元至少需要的硬币数目(dp[m])相比较,取较小的存入dp[m]。

这里可能就会有人问了,为什么还要和dp[m]比较后再存入dp[m],正如上面的例子,因为我们在凑够m元时,可能有多种可行的方案,我们要比较出哪一种方案所需硬币数目最小。例如在4种硬币1、3、5、7元凑8元的时候会有三种方案,1)8个1元;2)3+5元;3)1+7元。我们得从中找到我们所要的答案。(如果用贪心算法的话可能会错过最优解)

有了动态转移方程,问题基本就算解决了。当然,Talk is cheap,show me the code!

C++动态规划算法代码:

#include

using namespace std;

int main()

{

int coins[10] = {0}; //硬币面值数组,由于题目给出不超过10种,所以我申请了10。

int money = 0; //待凑钱的数值*/

int kind = 0; //钱币种类数目*/

while(1)

{

cin >> money;

if(0 == money)break; //结束标志

int dp[money+1]; //动态规划数组

dp[0] = 0; //初始化第一个元素为0,因为要凑0元需要0个钱币

cin >> kind; //硬币面值种类数

for(int k=0; k

{

cin >> coins[k]; //读入硬币面值,存入数组coins[]

}

for(int i = 1; i <= money; i++) dp[i] = 99999; //初始化数组dp[],设置dp[i]等于无穷大

for(int i = 1; i <= money; i++) //从凑1元开始,一直算到money元为止。

{

for(int j = 0; j < kind; j++)

{

if(i >= coins[j])

{

dp[i] = min(dp[i- coins[j] ] + 1, dp[i]);

}

/*****也可以写成******

if(i >= coins[j] && dp[i - coins[j]] + 1 < dp[i])

{

dp[i] = dp[i- coins[j] ] + 1;

}

自己干了,不用麻烦min()函数

*/

}

}

if( dp[money] == 99999 )

{

cout << "Impossible"<< endl;

}

else

{

cout << dp[money] << endl;

}

}

return 0;

}

da505d18ea8df5005e2cd0bd40d2f8ee.png图1-1 凑0-8元所需最少钱币

如图1-1所示,有4种面值的钱币1元、3元、5元、7元时,从凑0元到凑8元至少所需钱币数。

总结:

使用动态规划算法解决此题时,能全面的考虑到所有情况,从而找到最优解。但是相对于贪心算法来说时间和空间复杂度都会增加。对于这道题,贪心算法的时间复杂度为n,动态规划算法的时间复杂度为N*M(N为钱币种类数,M为金额)。这两个算法有什么区别呢?如图1-2所示。

369947d6077eb600291c16f828db9c71.png图1-2 贪心算法和动态规划区别

动态规划算法不是一个具体的算法,动态规划算法要求我们具体问题具体分析。把一个大的问题变为一个和它同质的(除了规模变小,其他都一样)小规模问题。然后推导出递推公式(状态转移方程)。这是关键。那么这个推导递推公式的能力怎么获得呢?

动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不像搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。                                                                                   ——From Baidupedia

最后一点总结,写完东西一定要保存,刚刚去吃饭忘记保存,结果重新写了俩多小时。

这篇关于java最少需要多少张纸币_最少钱币数(凑硬币)详解-2-动态规划算法(初窥)-编程练习题(100)...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/651961

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory