最少硬币问题.doc

最少硬币问题.doc

ID:56802774

大小:59.00 KB

页数:3页

时间:2020-07-12

最少硬币问题.doc_第1页
最少硬币问题.doc_第2页
最少硬币问题.doc_第3页
资源描述:

《最少硬币问题.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)动态规

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

3、第i个硬币拿出去得到的一个最少的找硬币数+1,和原硬币数相比最小的那个就是结果。(4)另外一种思路,可以将所有的硬币价值都放在一个数组,就变成了0-1背包问题,所需考虑的就是放不放的问题。算法步骤:#includeusingnamespacestd;intmin(inta,intb);intmain(){实验内容(算法、程序、步骤和方法)intn;//n种不同面值的硬币intm;inti,j,k;cout<<"请输入有几种不同的面值:";cin>>n;int*t=newint[n+1];//硬币的面值存放在t数组中--价值int*c

4、oin=newint[n+1];//可以使用的硬币个数存放在coin中--个数cout<<"请输入"<>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++)//硬币的面值的个数fo

5、r(k=m;k>=t[i];k--){dp[k]=min(dp[k-t[i]]+1,dp[k]);}cout<<"最少需要用到的硬币个数是:";if(dp[m]==99999)cout<<-1<

6、j],1+c[i][j-T[i]]}。小结实验心得:通过这次实验,是我对0-1背包问题和动态规划法有了更深的理解。设计动态规划法第一步就是要刻画好最优子结构。当问题的最优解包含子问题的最优解时,称该问题有最优子结构性质。以自底向上的地从子问题的最优解构造出整个问题的最优解。指导老师评议成绩评定:指导教师签名:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。