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

首页算法课ppt，贪心算法

算法课ppt，贪心算法

算法

5星 · 超过95%的资源需积分: 10 113 浏览量更新于2023-05-31 评论收藏 887KB PPT 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

64页

算法课ppt，贪心算法，贪心算法，贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法

资源详情

资源评论

资源推荐

Greedy Method

•

A greedy algorithm always make the choice that

looks best at every step. That is, it makes local

optimal solution in the hope that this choice will lead

to a globally optimal one.

–

I make the shortest path to the target at each step.

Sometime I win, sometime I lose.

Examples of Greedy

Algorithms

•

Scheduling

–

Activity Selection

–

Minimizing time in system

–

Deadline scheduling

•

Graph Algorithms

–

Minimum Spanning Trees

–

Dijkstra’s (shortest path) Algorithm

•

Other Heuristics

–

Huffman coding

–

Coloring a graph

–

Traveling Salesman Problem

–

Set-covering

–

Subset-sum problem

例 [ 找零钱 ] 一个小孩买了价值少于 1 元的糖，并将 1 元的钱交给售货员。

售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为 25

分、 10 分、 5 分及 1 分的硬币。售货员分步骤组成要找的零钱数，每次

加入一个硬币。

选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确

保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不

应使零钱总数超过最终所需的数目。

假设需要找给小孩 67 分，首先入选的是两枚 25 分的硬币，第三枚入选的不

能是 25 分的硬币，否则将不可行（零钱总数超过 67 分），第三枚应选择

10 分的硬币，然后是 5 分的，最后加入两个 1 分的硬币。

贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币

数目最少（至少是接近最少的数目）

Activity-Selection Problem

•

Problem: Given a set A = {a

, a

, …, a

} of n activities

with start and finish times (s

, f

), 1 ≤ i ≤ n, select max

imal set S of “non-overlapping” activities.

–

One can think of the problem as corresponding to schedulin

g the maximal number of classes (given their start and finis

h times) in one classroom.

•

Solution:

–

Sort activities by finish times (let a

, a

, …, a

denote sorted

sequence)

–

Pick first activity a

–

Remove all activities with start time before finish time of a

–

Recursively solve problem on remaining activities.

Activity Selection

•

Here is the problem from the book:

–

Activity a

starts at s

= 1, finishes at f

= 4.

–

Activity a

starts at s

= 3, finishes at f

= 5.

–

Activity a

starts at s

= 0, finishes at f

= 6 ...

•

Got the idea?

–

The set S is sorted in monotonically increasing order of finis

h time.The subsets of {a

, a

} and {a

, a

}are mutuall

y compatible.

剩余63页未读，继续阅读

loy_ma

2012-12-03

讲得挺详细的，不错，学习了

hayu724

粉丝: 0
资源: 2

上传资源快速赚钱

我的内容管理收起

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

会员权益专享

算法课ppt，贪心算法

评论1

会员权益专享

最新资源

算法课ppt，贪心算法

评论1

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

算法设计之贪心算法ppt

机器学习算法总结ppt

迭代算法和贪心算法的不同

制作一个介绍GA算法的ppt

动态规划算法和贪心算法分治算法区别

acwing算法基础课

yolo算法讲解ppt

DES算法& AES算法.ppt

近似算法和贪心算法有什么不同

遗传算法_蚁群算法_模拟退火算法_粒子群算法.ppt

贪心算法，动态规划算法，分治算法的区别

最小生成树kruskal算法java贪心算法

请阐述分治算法、动态规划算法、贪心算法三者的共同点与区别，以及它们都有哪些优势和劣势？

Kalman 滤波算法综述 ppt

贪心算法经典例题.doc

Change detection算法PPT

萤火虫算法讲解PPT.pptx

python 贪心算法

会员权益专享

最新资源