动态规划算法求解硬币找零问题
动态规划的基本思想是将待求解问题分解成若干个子问题,先求解子问题,并将这些子问题的解保存起来,如果以后在求解较大子问题的时候需要用到这些子问题的解,就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式,例如保存在数组中。
用一个实际例子来体现动态规划的算法思想——硬币找零问题。
硬币找零问题描述:现存在一堆面值为 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)的这一个硬币。
下面用代码实现并测试一下:
public class CoinsChange { /** * 硬币找零:动态规划算法 * * @param values * :保存每一种硬币的币值的数组 * @param valueKinds * :币值不同的硬币种类数量,即coinValue[]数组的大小 * @param money * :需要找零的面值 * @param coinsUsed * :保存面值为i的纸币找零所需的最小硬币数 */ public static void makeChange(int[] values, int valueKinds, int money, 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[] { 25, 21, 10, 5, 1 }; // 需要找零的面值 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
上面的代码并没有给出具体应该是哪几个面值的硬币,这个可以再使用一些数组保存而打印出来。
分享到:
相关推荐
动态规划算法求解TSP 用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用...
动态规划启发式算法求解时变车辆调度问题
经典算法问题-TSP商旅问题(Traveling Salesman Problem),它是数学领域中著名问题之一。...代码包含遗传算法和动态规划来求解这个问题,里面有完整源代码,并且有详细注释,还有两者的比较分析。
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解求得原问题的解。与分治法不同的是,适合于动态规划法求解的问题,经分解求得的子问题往往不是互相独立...
如题,动态规划法求解0-1背包问题实验报告 大二算法作业 使用java语言实现 内容框架:问题描述 思路分析 实例分析 实验原码及运行结果 实验心得
以下是使用动态规划算法求解旅行商问题(TSP)的Python代码。为了可视化每次迭代的最优值、最差值和平均值,我们使用matplotlib库。python import networkx as nx import pandas as pd import gurobipy as grb ...
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立...
最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
代码是使用动态规划算法求解制作武器的最优方案,是算法导论中钢条切割问题的改进,修改其中两个数组就可以实现自己需要的动态规划算法的求解
对于给定的字符串A和B,给定其字串的内容和空格相对字符的距离,使用动态规划算法求解两字符串的扩展距离。
会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf
算法设计与分析作业:动态规划———硬币问题源码
实验目标实验目标: ...(1)掌握用动态规划方法求解实际问题的基本思路。 (2)进一步理解动态规划方法的实质,巩固设计动态规划算法的基本步骤。 实验任务: (1) 实现0-1背包问题的动态规划算法
(1)设计动态规划算法求解资源分配问题,给出算法的非形式描述。 (2) 在Windows环境下用C 语言实现该算法。计算10个实例,每个实例中n=30, m=10, Ci j为随机产生于范围(0,103)内的整数。记录各实例的数据及...
计算机算法设计与分析动态规划法求解0-1背包问题的改进算法完整解释
利用动态规划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。因此,动态规划技术越来越成为解决许多重要的应用问题的关键技术。例如,用动态规划解决0-1背包问题、图像数据压缩、矩阵连乘、有向...
引言车辆路径 问题( ve h ic ler out i ngp rob le m,) 是一类典型的 组合优化 问题丨, 最 早在1 95 9 年由D ant
01背包问题动态规划,动态规划求解找零问题和背包问题C++代码
对基于动态规划的TSP问题的求解 ,这个源码很好的说明其中的求解过程,以及数据结构的设计问题