最少硬币问题

实验报告学号： 姓名： 班级：课程名称算法设计与分析实验课时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时，若fi为0，即还未赋过值，且ci-k不为0，即从i元钱中刨去k元后剩下的钱数可以找开，则ci=ci-k+1，若fi不为0，即已赋过值，则fi为fi-k+1和fi中较小的。 （2）硬币问题就是一个多重背包问题。 （3）动态迁移方程为 dpk = mindpk-ti+1,dpk 将第i个硬币拿出去得到的一个最少的找硬币数+1，和原硬币数相比最小的那个就是结果。 （4） 另外一种思路，可以将所有的硬币价值都放在一个数组，就变成了0-1背包问题，所需考虑的就是放不放的问题。 算法步骤：#include using namespace std; int min(int a,int b); int main() 实验内容（算法、程序、步骤和方法） int n; /n种不同面值的硬币 int m; int i , j ,k; coutn; int *t =new intn+1; /硬币的面值存 放在t数组中 - 价值 int *coin = new int n+1; /可以使用的硬币个数存放在coin中-个数 cout请输入n组硬币的面值和对应的个数（中间用空格隔开）:endl; for(i = 1 ;iticoini; coutm; int dp20002=0 ; /dpi 用来记录钱数为i时的最少的硬币数 for(i=1;i=m;i+) dpi = 99999; for(i = 1 ;i = n ; i+) /硬币面值的种数 for(j = 1 ; j = ti ; k- ) dpk = min(dpk-ti +1,dpk); cout最少需要用到的硬币个数是:; if(dpm = 99999)cout-1endl; else coutdpm个endl; int min(int a,int b) return ab?a:b; 三、复杂度分析 时间复杂度：O（nL） 空间复杂度：O（L）数据记录和计算结 论（结 果）用动态规划法能够很好地解决最少银币问题，时间复杂度为O（nL），空间复杂度为O（L）。其中计算递归的表达式为：cij=minci-1j,1+cij-Ti。小结实验心得：通过这次实验，是我对0-1背包问题和动态规划法有了更深的理解。设计动态规划法第一步就是要刻画好最优子结构。当问题的最优解包含