logo资料库

c语言贪心算法.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.14M 资料格式：doc 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    计算机与信息科学系 实验报告 2011 – 2012 学年第 2 学期 任课老师： 课程名称 结构化程序设计 班级 座号 姓名 实验题目 贪心算法设计 实验时间 实验开始日期： 报告提交日期： 2012-5-8 实验目的、要求 1．利用贪心策略解决背包问题。现有载重为 M 公斤的背包和 n 种货物。第 i 种货物的重量为 Wi，它的总价值为 Pi，假定 M、Wi、Pi 均为整数。设计程序 给出装货方法，使装入背包的货物总价值达到最大。 2．设计实现超市收银程序，假设顾客在超市购买各种商品，来到收银台结 账，收银员具有面值为 100，20，10，5 和 1 元的纸币和各种面值为 5 角、2 角、 1 角的硬币。设计程序计算顾客各种所买商品的钱数，并根据顾客所付的钱数输 出零钱的数目及要找的各种货币的数目。 实验步骤与内容 按如下顺序写： 1、 主要设计思想； 1.中，其实问的关键在于那个物品的‘性价比’最高，就优先把那个物品装满，这就是 主要的思路，剩下的问题的就是排列‘性价比’，从性价比最高的装一直到性价比最低 的装，中间判断下，重量是否已满。 2.中 将零钱一步一步取整就可以了 A=总数/100，B=100*A/50……依次类推即可。 2、 所有函数的简要说明； 1 核心算法： 当背包剩下的重量不足以装整个货物时 for(i=1;l!=0;i++) { if (l<=w[i]) { } sum=sum+l*v[i]; y[i]=l; break; l=l-w[i]; 减去装入的重量 sum=sum+w[i]*v[i]; y[i]=w[i]; y[i]为每个货物装的重量 } { 2 核心算法 for(i=0;money[i]<=1;i++) 面值大于 1 元的找零 b=sum/(int)money[i]; printf("%.1f 元的找零%d 张\n",money[i],b); 1
    sum=sum-money[i]*b; } for(;money[i]!=-1;i++) 面值大于 1 元的找零 b=sum*10/(int)(money[i]*10); printf("%.1f 元的找零%d 张\n",money[i],b); sum=sum-money[i]*b; { } 试验过程记录 记录试验中遇到的困难及解决方法； 第二个题目中，没办法将找零面值小于 1 元的 解决：b=sum*10/(int)(money[i]*10); 实验结果记录以及与预期结果比较以及分析 记录每次实验结果以及分析情况 2
    总结以及心得体会 了解了贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出 最优值(或较优解)的一种解题方法。其实没什么特别的算法，或许是题目的难度 不够吧，哈哈，找到思路后就很容易做了。 指导老师评阅意见 填写内容时，可把表格扩大。实验的源程序代码（要有注释）附在表后。 //背包问题 #include 指导老师： 年 月 日 #include int main(void) { int l,n,i,j; float v[30],temp,w[30],m[30],y[30],sum=0; printf("请输入背包的重量："); scanf("%d",&l); printf("请输入货物种类："); scanf("%d",&n); printf("请输入各个货物的重量："); for(i=1;i<=n;i++) scanf("%f",&w[i]); 3
    printf("请输入各个货物的价值："); for(i=1;i<=n;i++) scanf("%f",&m[i]); for(i=1;i<=n;i++) v[i]=m[i]/w[i]; for(i=1;i
    printf("%.2f\n",y[i]); } printf("最大价值为:%.2f \n",sum); return 0; } //找零问题 #include #include int main(void) { int i,n,b; float q[30],sum=0,s,money[10]; printf("请输入商品件数："); scanf("%d",&n); printf("请输入每件商品的价格："); for(i=0;i
    sum=sum-money[i]*b; } for(;money[i]!=-1;i++) { b=sum*10/(int)(money[i]*10); if(b!=0) printf("%.1f 元的找零%d 张\n",money[i],b); sum=sum-money[i]*b; } return 0; } 6
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料