最少硬币问题(共3页).doc

精选优质文档-倾情为你奉上实验报告学号： 姓名： 班级：课程名称算法设计与分析实验课时2实验项目最少硬币问题实验时间实验目的 设有n种不同面值的硬币，各硬币的面值存于数组T1:n中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins1:n中。 对任意钱数0m20001，设计一个用最少硬币找钱m的方法。实验环境Visual C+实验内容（算法、程序、步骤和方法）1、 算法策略对于给定的1n10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0m20001，计算找钱m的最少硬币数。2、 算法设计（步骤）算法思想：（1）动态规划实现 长度为m的数组f1.m中存放一系列子结果，即fi为要凑的钱数为i时 ，所需的最少硬币数，则cm为所求; 当要找的钱数i(1im)与当前所试探的硬币面值k相等时，结果为1，即ci=1 ；当i大于当前所试探硬币面值k时