最少硬币问题

算法设计与分析实验报告实验报告学号：姓名：班级：课程名称算法设计与分析实验课时2实验项目最少硬币问题实验时间实验目的设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。实验环境VisualC++实验内容（算法、程序、步骤和方法）一、算法策略对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。二、算法设计（步骤）算法思想：（1）动态规划实现长度为m的数组f[1...m]中存放一系列子结果，即f[i]为要凑的钱数为i时，所需的最少硬币数，则c[m]为所求;当要找的钱数i(1im)与当前所试探的硬币面值k相等时，结果为1，即c[i]=1；当i大于当前所试探硬币面值k时，若f[i]为0，即还未赋过值，且c[i-k]不为0，即从i元钱中刨去k元后剩下的钱数可以找开，则c[i]=c[i-k]+1，若f[i]不为0，即已赋过值，则f[i]为f[i-k]+1和f[i]中较小的。（2）硬币问题就是一个多重背包问题。（3）动态迁移方程为dp[k]=min{dp[k-t[i]]+1,dp[k]}将第i个硬币拿出去得到的一个最少的找硬币数+1，和原硬币数相比最小的那个就是结果。（4）另外一种思路，可以将所有的硬币价值都放在一个数组，就变成了0-1背包问题，所需考虑的就是放不放的问题。算法步骤：#includeiostreamusingnamespacestd;intmin(inta,intb);intmain(){算法设计与分析实验报告实验内容（算法、程序、步骤和方法）intn;//n种不同面值的硬币intm;inti,j,k;cout请输入有几种不同的面值:;cinn;int*t=newint[n+1];//硬币的面值存放在t数组中--价值int*coin=newint[n+1];//可以使用的硬币个数存放在coin中--个数cout请输入n组硬币的面值和对应的个数（中间用空格隔开）:endl;for(i=1;in+1;i++)cint[i]coin[i];cout请输入要找的钱数m:;cinm;intdp[20002]={0};//dp[i]用来记录钱数为i时的最少的硬币数for(i=1;i=m;i++)dp[i]=99999;for(i=1;i=n;i++)//硬币面值的种数for(j=1;j=coin[i];j++)//硬币的面值的个数for(k=m;k=t[i];k--){dp[k]=min(dp[k-t[i]]+1,dp[k]);}cout最少需要用到的硬币个数是:;if(dp[m]==99999)cout-1endl;elsecoutdp[m]个endl;}intmin(inta,intb){returnab?a:b;}三、复杂度分析时间复杂度：O（nL）空间复杂度：O（L）算法设计与分析实验报告数据记录和计算结论（结果）用动态规划法能够很好地解决最少银币问题，时间复杂度为O（nL），空间复杂度为O（L）。其中计算递归的表达式为：c[i][j]=min{c[i-1][j],1+c[i][j-T[i]]}。小结实验心得：通过这次实验，是我对0-1背包问题和动态规划法有了更深的理解。设计动态规划法第一步就是要刻画好最优子结构。当问题的最优解包含子问题的最优解时，称该问题有最优子结构性质。以自底向上的地从子问题的最优解构造出整个问题的最优解。指导老师评议成绩评定：指导教师签名：