找零钱问题的最优子结构性质及动态规划算法分析与设计
本实验的题目是找零钱问题,要求设计一个算法,用最少的钞票张数找给顾客。每种钞票都有足够的张数。首先需要进行符号的说明,n表示零钱的种数。 本实验采用了两种动态规划算法来解决这个问题。首先是自底向上的动态规划算法,然后是备忘录法。下面将对这两种算法进行详细的描述。 自底向上的动态规划算法的主要思想是,从较小的子问题开始解决,逐步推导出较大的子问题的解,最终得到整个问题的解。具体步骤如下: 1. 创建一个长度为amount+1的一维数组dp,dp[i]表示得到金额为i所需的最少钞票张数。 2. 初始化dp数组,将所有元素初始化为正无穷大,除了dp[0]设置为0。 3. 遍历钞票面额的种类,对于每一种面额,从金额1开始,计算得到的最少钞票张数。假设当前面额为coin,遍历金额为i的情况,更新dp[i] = min(dp[i], dp[i-coin]+1)。 4. 输出dp[amount],即找零所需的最少钞票张数。 备忘录法是动态规划的一种优化方法,其主要思想是通过记录已经计算过的子问题的解来避免重复计算。具体步骤如下: 1. 创建一个长度为amount+1的一维数组memo,memo[i]表示金额为i时的最少钞票张数。初始情况下所有元素设置为-1。 2. 创建递归函数helper,接收一个参数amount,返回金额为amount时的最少钞票张数。 3. 在helper函数中,首先判断是否已经计算过memo[amount]的值,如果计算过则直接返回memo[amount]。否则,将memo[amount]设置为正无穷大,然后遍历钞票面额的种类,计算得到金额为amount所需的最少钞票张数,并更新memo[amount]的值。 4. 返回memo[amount],即找零所需的最少钞票张数。 实验要求至少运行3组不同的输入数据,并用两种方法求解,即动态规划和备忘录法。 本实验使用Java编程语言完成算法设计和程序设计,并成功调试通过。 总结以上所述,本实验通过自底向上的动态规划算法和备忘录法解决了找零钱问题,并满足了实验要求。
![](https://csdnimg.cn/release/download_crawler_static/86384118/bg6.jpg)
剩余26页未读,继续阅读
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://profile-avatar.csdnimg.cn/8bea0dde30b140e199236eb7cf9bc5b7_weixin_35833704.jpg!1)
- 粉丝: 22
- 资源: 311
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)