文档介绍：实验报告学号: 姓名: 班级:课程名称算法设计与分析实验课时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(1<i<m)与当前所试探的硬币面值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,和原硬币数相比最小的那个就是结果。另外一种思路,可以将所有的硬币价值都放在一个数组,就变成了0-1背包问题,所需考虑的就是放不放的问题。算法步骤:#include<iostream>usingnamespacestd;intmin(inta,intb);intmain(){实验内容(算法、程序、步骤和方法)intn;//n种不同面值的硬币intm;inti,j,k;cout<<"请输入有几种不同的面值:";cin>>n;int*t=newint[n+1];//硬币的面值存放在t数组中--价值int*coin=newint[n+1];//可以使用的硬币个数存放在coin中--个数cout<<"请输入"<<n<<"组硬币的面值和对应的个数(中间用空格隔开):"<<endl;for(i=1;i<n+1;i++)cin>>t[i]>>coin[i];cout<<"请输入要找的钱数m:";cin>>m;intdp[20002]={0};//dp[i]用来记录钱数为i时的最少的硬币数for(i=1;i<=m;i++)dp[i]=99999;for(i=1;i<=n;i++)//硬币面值的种数for(j=