




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、CS-SWPUn不同面额硬币,个数不限q¥0.25、0.1、0.05、0.01n兑换钱数q¥ 0.63n目标:用于兑换的硬币个数最少1.穷举所有可能性2.按面值从大到小选择硬币兑换按面值从大到小选择硬币兑换n0.63 = 2 * 0.25 + 1 * 0.1 + 3 * 0.01CS-SWPUn按面值从大到小选择硬币!按面值从大到小选择硬币!q选用的硬币面额越大,需要用于兑换的硬币个数就选用的硬币面额越大,需要用于兑换的硬币个数就越少越少q这就是贪心策略!这就是贪心策略!CS-SWPU /需兑换钱数a; /可用硬币面额集合d; while ( 兑换未完成 ) 选出当前可用的最大面额 x ; 用
2、面额 x 执行兑换:使用数量c、兑换金额e ; 累计硬币使用总量 sum = sum + c ; 每种面额只考察了一次,效率高!每种面额只考察了一次,效率高!如何知道兑换未完成?CS-SWPU /需兑换钱数a; /可用硬币面额集合d; while ( 剩余金额剩余金额0 ) 选出当前可用的最大面额 x ; 用面额 x 执行兑换:使用数量c、兑换金额e ; 累计硬币使用总量 sum = sum + c ; 剩余金额剩余金额 = 剩余金额剩余金额 - e; 剩余金额如何表示?面额集合如何表示?兑换量如何计算?兑换方案如何表示?兑换方案如何表示?CS-SWPU输入:d :面额数组(值:大小),n:面
3、额种数,a:需兑换金额输出:最少的兑换硬币个数int greedyChange (int d , int n, int a) int i = 1; int sum = 0 ; while ( a 0 ) int c = a / di ; /计算面额为 di 的硬币兑换量 (整除) sum = sum + c ; /累计硬币使用总量 a = a c*di ; /计算剩余金额 i = i + 1; /考察下一面额 return sum ; / 结果:用于兑换的硬币总数每种硬币的具体兑换量?CS-SWPUint greedyChange (int d ,int n,int a) int i = 1;
4、 int sum = 0 ; while ( a 0 ) int c = a / di ; a = a c*di ; sum = sum + c ; i = i + 1; return sum ;d = 25, 10, 5, 1,a = 631) i=1:a = 63 0 c = a / d1 = 2 a = a c * d1= 13,sum = 22) i =2:a = 13 0 c = a / d2 =1 a = a c * d2 = 3,sum = 33) i=3:a = 3 0 c = a / d3 = 0,d3 = 5 a = a c * d3 = 3,sum = 34) i=4:a
5、 = 3 0 c = a / d4 = 3 a = a c * d4 = 0,sum = 65) i=5:a=0,算法终止CS-SWPUn贪心策略q效率高n每种面额只处理一次,无需考察不同的面额组合q动态规划:系统考察所有组合q有局限!有局限!n面额:¥0.11, 0.05, 0.01,兑换: ¥ 0.15q还能使用贪心策略吗?还能使用贪心策略吗?CS-SWPUn总是作出在当前看来最好的选择q在某种意义上的局部最优选择,不从整体最优考虑n希望得到的最终结果整体最优q单源最短路经问题,最小生成树问题等n不一定总能得到整体最优解不一定总能得到整体最优解q这时的结果是最优解的很好近似这时的结果是最优
6、解的很好近似n可行、较优解可行、较优解CS-SWPUn动态规划q对每种面额检查其选与不选的情况下,兑换是否最优!q如何应用动态规划?n回顾动态规划的步骤q证明问题满足最优子结构性质q定义与最优解相关的最优值q推导最优值计算递归式q根据计算递归式设计算法,计算最优值,同时保存最优解相关信息q根据上一步得到的信息,构造最优解CS-SWPUn动态规划的步骤q证明问题满足最优子结构性质n证明贪心算法正确性时,已经得证q定义与最优解相关的最优值q推导最优值计算递归式n怎么做?n提示:参照0-1背包的动态规划算法qm(i, j) 可选物品 i, i +1, , n,背包容量 jqc (i, j) 可选面额
7、可选面额 di, di +1, , dn,需兑换金额,需兑换金额 jCS-SWPUn假定q面额数组:d1d2dn=1q需兑换金额 an最优值c (i, j)q可选面额 di, di +1, , dn,需兑换金额 jq1 i n,0 j an递归计算式q当di j 时,c (i, j) = c ( i+1, j )q当di j 时,c (i, j) = min c(i+1, j), j / di + c(i, j mod di) CS-SWPUdynamicChange(d , n, a, c ) for (j=0; j=1; j-) /逐行向上 for (j=0; j j ) /面额di 超过金额 j cij = ci + 1j; else if ( ci+1j j/di + ci j % di ) /不选面额di更小 cij = ci + 1j; else cij = j/di + ci j % di ; /选
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- BLX-3887-生命科学试剂-MCE
- 宁夏葡萄酒与防沙治沙职业技术学院《中国文学导读》2023-2024学年第一学期期末试卷
- 沧州师范学院《综艺节目编导》2023-2024学年第一学期期末试卷
- 内蒙古师范大第二附中2024年化学九年级第一学期期末达标测试试题含解析
- 武昌首义学院《中外经典戏剧作品选讲》2023-2024学年第一学期期末试卷
- 2024年河北省石家庄市桥西区九年级化学第一学期期末质量检测模拟试题含解析
- 共享出行信用保险与信用体系构建研究报告
- 2025全球劳动力趋势报告第1期
- 2024年山东省青岛市广雅中学七年级数学第一学期期末达标检测模拟试题含解析
- 遵义医科大学《透过影像看健康》2023-2024学年第一学期期末试卷
- 码头承包经营合同
- DB37T2367-2022《回弹法检测砌筑砂浆抗压强度技术规程》
- 对生活饮用水的卫生监督
- 2022江苏省中央财政补贴型奶牛养殖保险条款
- 乐山市口腔医院门诊牙科诊所医疗机构企业地址名单目录
- WTO世界贸易组织概论期末复习题
- 外贸业务员KPI考核量表
- 智慧物业管理系统解决方案
- 幼儿园教育活动设计与指导幼儿园教育活动设计的基本模式
- 数字声音广播7-drm技术系统与二
- 嵌顿疝病人应急预案
评论
0/150
提交评论