作业帮大币找零钱之贪心算法
来源：学生作业帮助网 编辑：作业帮 时间：2024/09/24 06:23:45 优秀作文
篇一：找零钱问题的贪心算法
找零钱问题的贪心算法
问题描述：
当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）
问题分析：
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
//找零钱算法
//By falcon
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分 //输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案 public static int[] zhaoqian(int m[],int n)
{
int k=m.length;
int[] num=new int[k];
for(int i=0;i { num=n/m; n=n%m; } return num; } public class zhaoqian { public static void main(String[] args) { int m[]={25,10,5,1}; int n=99; int[] num=new int[m.length]; num=zhaoqian(m,n); System.out.println(n+"的找钱方案："); for(int i=0;i System.out.println(num+"枚"+m+"面值"); } public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;i num=n/m; n=n%m; } return num; } } 篇二：运用贪心算法求解找零钱问题 运用贪心算法求解找零钱问题 1题目分析 我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。 2算法构造 用需要找的钱除以25取整就是需要的25的个数，用除以25的余数除以10取整就是需要10个数，依此类推求出找零钱方案。 3算法实现 #include using namespace std; int main(){ int c ; int a25=0,a10=0,a5=0,a2=0,a1=0; cout<<"请输入要找的零钱:"< cin>>c; a25=(c/25); a10=(c%25)/10; a5=(c%25)%10/5; a2=(c%25)%10%5/2; a1=(c%25)%10%5%2; cout<<"需要找以下几种零钱:"< cout<<"25分的"< cout<<"10分的"< cout<<"5分的"< cout<<"2分的"< cout<<"1分的"< 4运行结果 篇三：贪心算法 找零钱问题 学 号 《算法设计与分析》 实验报告三 学 专 指 成 生业导、姓班教名 级 师 绩 电子与信息工程系 实验三：贪心算法运用练习 一、实验目的 本次实验是针对贪心算法运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验二_学号_姓名”， 如“《算法设计与分析》实验二_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验二_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2012年12月7日16:00。 三、 实验项目 1．传统的找零钱问题的算法及程序实现。 2．特殊的0-1背包问题的求解：本次求解的0-1背包问题的特点为每种物品各有M件，已知每个物品的单位价值，求使得所获价值最大的装包方案。 四、 实验过程 找零钱问题: #include using namespace std; void Zl(double num) { int leave=0; int a[8]; leave = (int)(num*10)%10; a[1] = leave/5; } a[0] = (leave%5)/1; a[7] = num/50; a[6] = ((int)num%50)/20; a[5] = (((int)num%50)%20)/10; a[4] = ((((int)num%50)%20)%10)/5; a[3] = (((((int)num%50)%20)%10)%5)/2; a[2] = ((((((int)num%50)%20)%10)%5)%2)/1; if(a[0]!=0) cout<<"需要找的0.1元个数为："< void main () { } double num; cout<<"请输入你需要找的零钱数："< 五、实验总结 篇四：证明人民币找零问题贪心算法正确性 证明人民币找零问题贪心算法的正确性 问题提出： 根据人们生活常识，我们到商店里买东西需要找零钱时，收银员总是先给我们最大面值的，要是不够再找面值小一点的，直到找完为止。这就是一个典型的贪心选择问题。 问题描述： 当前有面值分别为100 元、50 元、20 元、10 元、5元、1元, 5角, 2角、1角的人民币。证明人民币在找零时（1-99元）符合贪心算法，即证明此问题满足贪心算法的两个基本要素：即最优子结构性质和贪心选择性质。 问题证明： 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。在人民币找零问题中，其最优子结构性质表现为： 设c[i]是各面额人民币使用的数量，S[i]是商品价格为n时的最优解，数量为K。现在设某面值的人民币数量减一：S[j]=S[j]-1，则新的S[i]为n-c[j]的最优解，纸币数K-1. 否则，设T[i]是n-c[j]的最优解，纸币数为m，即m 设纸币面额100,50,20,10,5,2,1元的数量依次为A,B,C,D,E,F,G，则根据贪心算法思想得到的解应依次保证max（A），max（B），max（C），max（D），max（E），max（F），max（G）。假设存在更优的算法，使得所用的纸币数更少，即数量至少小于或等于A+B+C+D+E+F+G-1。那么在纸币总数减少的情况下保证总额不变只能增大相对大面额纸币的数量并减少小面额纸币数量。而由贪心算法知max（A）已经是最大的了，以此类推，max（B），max（C），max（D），max（E），max（F）均应为最大数量了，所以贪心算法得到的解是最优解，即满足贪心选择性质。 综上所述，人民币找零问题满足贪心算法。 篇五：贪心算法的实验报告 福建工程学院计算机与信息科学系 实验报告 1 2 3 4 5