最少硬币问题.doc

《最少硬币问题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告学号：姓名：班级：课程名称算法设计与分析实验课时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

2、]中存放一系列子结果，即f[i]为要凑的钱数为i时，所需的最少硬币数，则c[m]为所求;当要找的钱数i(1

3、个就是结果。（4）另外一种思路，可以将所有的硬币价值都放在一个数组，就变成了0-1背包问题，所需考虑的就是放不放的问题。算法步骤：#includeusingnamespacestd;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<<"请输入"<

4、>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=1;j<=coin[i];j++)//硬币的面值的个数for(k=m;k>=t[i];k--){dp[k]=min(dp[k-t[i]]+1,dp[k]);}cout<<"最少需要用到的硬币个数

5、是:";if(dp[m]==99999)cout<<-1<

6、解包含子问题的最优解时，称该问题有最优子结构性质。以自底向上的地从子问题的最优解构造出整个问题的最优解。指导老师评议成绩评定：指导教师签名：