java硬币兑换_java动态规划取硬币问题_韩冰Bill的博客-程序员资料

技术标签: java硬币兑换  

最近一直在研究动态规划的问题。今天遇到了取硬币问题。

其实动态规划还是,我从底部向顶部,依次求出每个状态的最小值,然后就可以标记上。

这道题目就是,假如有1,5,7,10这四种币值的硬币,我取14元,取的硬币数最少要多少张。

其实动态规划就是要求出状态转移方程,就好比我的上一个博客的求最短路径的问题。而这道取硬币问题呢。如果我的硬币大于有的币值,那么就能状态转移

转移为temp[i-weizhi[j] + 1。temp[]是用来存放每种币值的最小数目。weizhi[]是用来存放币值。比如说吧,temp[0]表示取0个币值要0次,temp[1] 中1只大于1,所以能取1枚硬币。那么转换成temp[1-1]+1,取1次

temp[2]呢,2也是只大于1,那么转化成temp[2-1]+1......到temp[5]就不一样了,temp[5]中的5大于1,所以可以取temp[5-1]+1 = 5 ,而也可以取temp[5-5]+1 = temp[0]+1 = 0+1 = 1。照这种思想完全可以编出代码来了。但是这里涉及到一个问题,我每次都需要比较我最小的一个,这时候直接用变量来存放就行了,千万别习惯性的想用数组,我开始就是想用数组,但是还越界了,下面是我的代码,其实那个for循环就是动态规划的核心。可以理解为填数字吧。今天这么晚了,明天给大家更新填数字的代码。

import java.util.Scanner;

public class 找零钱 {

public static void main(String[] args) {

Scanner scn = new Scanner(System.in);

System.out.println("请输入想计算多少枚硬币:");

int n = scn.nextInt();

int temp[] = new int[n+1]; //存放每种硬币取的最少的取法

int weizhi[] = {1,5,7,10}; //四种硬币

//动态规划的核心,用for循环去填充每次能标记上的

for(int i=1;i

int minV = i; //初始化最小的为minV,因为最小取的硬币数量肯定不会比i还要大

for(int j=0;j

if(i>=weizhi[j]) { //取的硬币的数目比有的数目要大。

int k = temp[i-weizhi[j]] + 1; //状态转移方程,前面介绍的。

if(k

minV = k; //保存了,这一趟比较的最小的取的硬币值

}

}

}

temp[i] = minV;

}

System.out.println("至少需要" + temp[n] + "枚硬币");

}

}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_31026805/article/details/114617397

智能推荐

6步解决Redhat7.4配置本地源Yum_三朝看客的博客-程序员资料

Redhat7.4没有网络的情况下,就只能使用本地源。本地源的搭建需要挂载本地光盘。1、设置源。打开终端,以ROOT身份去执行。vim /etc/yum.repos.d/iso.repo[iso]name=yumformcdrombaseurl=file:///yum/cdromenable=1gpgcheck=0gpgkey=file:///yum/REM-GPG-KEY-red...

第一篇付费专栏之为什么要开通付费专栏_空心菜使者的博客-程序员资料_付费专栏 5000字

这是我的第一篇付费文章,我也不知道是否会有人看,为什么要开通付费专栏呢?一是今天我要写一片开发博客的时候,CSDN原来的写文章变成了创作中心。点击链接进去之后,出现如下画面我就好奇了,我的阅读量那么多,怎么一点收益也没有,而且我的博客确实也帮助了很多人。那我就开通一个付费专栏,看看能不能收到一份钱吧。这是一个原因,此外还有另外的原因就是,也是激励自己多多创作,证明自己的价值吧。在现...

报错module 'xlrd' has no attribute 'open_workbook'以及 python No such file or directory: 'results.xls'_贝影23号的博客-程序员资料

import xlrd失败data=xlrd.open_workbook('results.xls') 失败报错:AttributeError: module 'xlrd' has no attribute 'open_workbook'我的原因:发现创建的py文件名叫 xlrd.py ,这样导致在文件中找open_workbook方法,改文件名成xlrdtest.py,成功但是,接着,报错:  ...

FREESWITCH部署与功能配置_老衲不出家的博客-程序员资料_freeswitch放行主机路由

一.FreeSWITCH服务部署1.wget http://www.freeswitch.org.cn/Makefile && make install2.cd freeswitch3.运行./bootstrap.sh(作用:初始化环境)4.执行./configure(主要的作用是对即将安装的软件进行配置,检查当前的环境是否满足要安装软件的依赖关系,但并不是所有的tar包都是源代码...

字体图标,web页面常用图标_约嫦娥烤兔子的博客-程序员资料_定义图标字体js

在web开发过程中,我们常常需要用到图标,在一些前端框架中,也会带有自己的图标库,但是可能不够全面,这里我给大家街上一个我常用的图标库:阿里巴巴矢量图标库。官网地址:http://www.iconfont.cn/首先,我们需要登录,使用guihub账号,或者使用新浪微博账号登录就可以。登录后,在图标管理中选择“我的项目”,如下图所示: 选择新建项目的图标,新建一个项目。然后在阿...

随便推点

vue3 + elementplus后台管理系统 + vue3核心Api实现 + Vuex4从零实现_目标学完css的博客-程序员资料

vue3 + elementplus后台管理系统 + vue3核心Api实现 + Vuex4从零实现所有源码放在github上,方便大家使用和学习。一、vue3-compositionApi-elementPlus-admin项目只包含框架的搭建,功能的完整封装,不包含任何业务组件。开箱即用。最新版的组合式api + 新版路由 + 新版store的使用采用的是前端保存路由菜单,根据后台返回的角色信息,动态加载路由和菜单渲染webpack-dll分离第三方库element-plus的全局自定

Line Renderer的一些重要参数_同灯花城的博客-程序员资料_linerender材质

Cast Shadows: 是否投射阴影。Receive Shadows: 是否接收阴影。Materials :设置材质,这里可以设置多个材质, line就是上面我们创建的材质,这里我给line这个材质涂上了红颜色。Positions:这个属性就比较重要了,它是专门设置线段在3D 世界中的点的坐标,size 设置点的数量 为3 那么将会有3个点,Element 0  Element...

Creating a Simple CRUD App With Yii2 用 Yii2 创建一个简单的 CRUD (增删改查)应用_YII2er的博客-程序员资料_79257.site-22

原文来自http://www.yiiframework.com/wiki/490/creating-a-simple-crud-app-with-yii2因为翻译能力有限,所以采用双语对照的形式,有译得不好的地方请多原谅。Creating a SimpleCRUD App With Yii2 (Revised 12/20/2013)用 Yii2创

leetcode算法83.删除排序链表中的重复元素_给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返_旷世奇才李先生的博客-程序员资料

????????????哈喽!大家好,我是【学无止境小奇】,一位热爱分享各种技术的博主!????????????【学无止境小奇】的创作宗旨:每一条命令都亲自执行过,每一行代码都实际运行过,每一种方法都真实实践过,每一篇文章都良心制作过。【学无止境小奇】的博客中所有涉及命令、代码的地方,除了提供图片供大家参考,另外会在图片下方提供一份纯文本格式的命令或者代码方便大家粘贴复制直接执行命令或者运行代码。????????????如果你对技术有着浓厚的兴趣,欢迎关注【学无止境小奇】,欢迎大

c语言memset( amp,memset_许九祀的博客-程序员资料

[求助]memset[求助]memset我在visualc++中编写的C程序用到函数memset(),但是找不到头文件mem.h,该怎么办?请各位帮忙解决一下color='#FF8000'>----------------解决方案--------------------------------------------------------...3热度【求助】memset();函数为什么失灵...

Android中View和ViewGroup事件分发拦截机制完美分析_加油勇士的博客-程序员资料_安卓view拦截所有事件

出自:http://www.cnblogs.com/linjzong/p/4191891.htmlTouch事件分发中只有两个主角:ViewGroup和View。Activity的Touch事件事实上是调用它内部的ViewGroup的Touch事件,可以直接当成ViewGroup处理。View在ViewGroup内,ViewGroup也可以在其他ViewGroup内,这时候把内部的

推荐文章

热门文章

相关标签