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

文库首页课程资源讲义贪心法的PPT

贪心法的PPT

需积分: 9 2 下载量 179 浏览量 2016-01-27 11:38:35 上传评论收藏 634KB PPT 举报

温馨提示

试读

57页

详细的算法设计PPT，非常适合刚入门的人学习，快来下载吧

资源推荐

资源详情

资源评论

4—

贪心法

Greedy Approach

陆伟

College of Software and Microelectronics

算法设计与分析

Introduction to the Design and Analysis of Algorithms

August 7, 2021

Northwestern Polytechnical University

Lu Wei 2

Lecture Overview

1. 贪心算法的基本思想

2. 贪心算法的设计要素

3. 贪心法的正确性问题

4. 应用实例

5.$ 贪心算法得不到最优情况的处理

6. 贪心算法的理论基础

7. 总结

贪心算法的基本思想



当一个问题具有最优子结构性质时，可用动态规

划方法求解，但有时会有更简单有效的方法。



例如

假设有 4 种硬币，它们的面值分别为二角五分、一角、五分

和一分，现要找给顾客六角三分钱，问如何选取个数最少

的硬币？

贪心算法的基本思想

















niNx

yxv

,...2,1,

min





问题一般性描述：

假设有 n 种硬币，其重量分别为 w

, w

, …, w

，它们的面

值分别为 v

=1, v

, … , v

，现需要用这些硬币付款总钱数是

y ，

问如何选取硬币使得付款的硬币总重量最轻？

动态规划：设 F

(y) 表示用前 k 中硬币，总钱数为 y 的最小重

量

wyF

)( 















})({min)(

1111























kkkkk

xwxvyFyF

与投资或 0-N 背包问

题类似时间复杂度

O(ny

) 或 O(ny)

贪心算法的基本思想



经常性做法

假设有 4 种硬币，它们的面值分别为二角五分、一角、五分

和一分，现要找给顾客六角三分钱，问如何选取个数最少

的硬币？

2 个二角五分， 1 个一角， 3 个一分。

过程：。。。

若硬币的面值改为一角一分、五分和一分，要找给顾客的

是一角五分，情况如何？

剩余56页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

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

xh_839486818

粉丝: 0
资源: 1

上传资源快速赚钱

我的内容管理展开

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

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

贪心法的PPT

贪心法.ppt

算法经典之一 贪心算法 ppt讲义

贪心算法PPT

贪心算法PPT~~

贪心法专题讲座

贪心法.pdf

贪心法（The Greedy Method）ppt

acm贪心法ppt

贪心算法之PPT讲解

贪心算法 ppt

贪心算法.ppt

基础算法贪心法PPT学习教案.pptx

ACM程序设计基础之贪心法PPT教学课件.pptx

数据结构--贪心法ppt

ACM程序设计基础之贪心法PPT学习教案.pptx

推选文档ACM程序设计基础之贪心法PPT.ppt

第7章 贪心法1

贪心算法贪心算法贪心算法

贪心_贪心算法_

贪心算法 贪心 算法 贪心的算法

贪心算法ppt

算法设计与分析--7贪心法.ppt

ACM程序设计基础之贪心法PPT课件.pptx

算法设计与分析：第6章 贪心法.ppt

贪心算法 ppt 很基础的讲解

计算机算法设计与分析：第三章 贪心法.ppt

最新资源

算法经典之一贪心算法 ppt讲义

第7章贪心法1

贪心算法贪心算法贪心的算法

算法设计与分析：第6章贪心法.ppt

计算机算法设计与分析：第三章贪心法.ppt