没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源C/C++贪心算法的理解和实现

贪心算法的理解和实现

贪心算法

需积分: 15 0 下载量 20 浏览量 2011-10-27 21:56:05 上传评论收藏 1.53MB PPT 举报

温馨提示

试读

62页

主要是一些算法的实现问题及如何去理解该类问题的解法

资源推荐

资源详情

资源评论

Algorithm Analysis and Design CS-SWPU

第

章贪心算法

Greedy Algorithm

最优化算法（ II ）

CS-SWPU

兑换硬币



不同面额硬币，个数不限



￥ 0.25 、 0.1 、 0.05 、 0.01



兑换钱数



￥ 0.63



目标：用于兑换的硬币个数最少

1. 穷举所有可能性

2. 按面值从大到小选择硬币兑换



0.63 = 2 * 0.25 + 1 * 0.1 + 3 * 0.01

CS-SWPU

兑换硬币



按面值从大到小选择硬币！



选用的硬币面额越大，需要用于兑换的硬币个数就

越少



这就是贪心策略！

CS-SWPU

硬币兑换的贪心算法

// 需兑换钱数＝ a;

// 可用硬币面额集合＝ d;

while ( 兑换未完成 ) {

选出当前可用的最大面额 x ;

用面额 x 执行兑换：使用数量＝ c 、兑换金额＝ e ;

累计硬币使用总量 sum = sum + c ;

}

每种面额只考察了一次，效率高！

如何知道兑换未完成？

CS-SWPU

硬币兑换的贪心算法

// 需兑换钱数＝ a;

// 可用硬币面额集合＝ d;

while ( 剩余金额 >0 ) {

选出当前可用的最大面额 x ;

用面额 x 执行兑换：使用数量＝ c 、兑换金额＝ e ;

累计硬币使用总量 sum = sum + c ;

剩余金额 = 剩余金额 - e;

}

剩余金额如何表示？

面额集合如何表示？

兑换量如何计算？

兑换方案如何表示？

剩余61页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

qingfeng_1988

粉丝: 0
资源: 2

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

贪心算法的理解和实现

贪心算法实现加油站问题

贪心算法 Dijkstra 单源最短路径

贪心算法实现删数问题

python 贪心算法的实现

贪心算法解决最优转载+最小生成树问题

山东科技大学算法设计与分析实验5：实现哈夫曼编码 源.cpp+报告

阿里算法实现

经典数据结构和算法的实现.zip

基础数据结构和算法的实现.zip

java数据结构和算法实现.zip

c语言课程设计道路交通灯控制系统.zip

一些常用的数据结构和算法的实现.zip

数据结构与算法（Java实现）.zip

常见算法和数据结构多语言实现.zip

Java实现常用数据结构和算法.zip

常见数据结构和算法的多语言实现。.zip

java实现基础的数据结构和算法.zip

数据结构与算法Java实现.zip

Qt上位机软件串口通讯，视频源码，免费下载

张玉生《C语言程序设计》双色版 C语言程序设计理论教材习题参考答案.pdf

代码随想录算法PDF.rar

cloud compare用户手册（中文+英文）

CRC8/CRC16/CRC32常见几个标准的算法及C语言实现

qt-everywhere-src-5.12.12源码

STM32F4 ADC采样FFT运算测试代码

Qt Qss三套样式文件 qss.zip

点云粗配准算法

C++读取excel数据

第十二届蓝桥杯大赛模拟赛（第三期）.pdf

最新资源

山东科技大学算法设计与分析实验5：实现哈夫曼编码源.cpp+报告