admin管理员组文章数量:1652188
文章目录
- 贪心算法(The Greedy Approach)
- 一、部分背包问题(The Fractional Knapsack Problem)
- 二、最短路径问题
- Dijkstra算法
- Kruskal算法
- 三、文件压缩(File Compression)
贪心算法(The Greedy Approach)
一、部分背包问题(The Fractional Knapsack Problem)
给定大小为s1、s2、…、sn的n个项目以及值v1、v2、…、vn和大小C、背包容量,目标是找到使总和最大化的非负实数x1、x2、…、xn:
对于每个项目,计算yi=vi/si,即其值与其大小的比率。按递减比例对物品进行分类,并尽可能多地从第一件物品到第二件物品填充背包,依此类推。
二、最短路径问题
Dijkstra算法
算法的伪代码如下:
Input:带权有向图G(V,E)
Output:顶点1到其他顶点的路径
X = {1}//走过的
Y = V - {1}//没走过的
m[1] = 0
for y = 2 to n://初始化
if y相邻于1:
m[y] = length[1,y]
else:
m[y] = inf
for j = 1 to n-1:
令y属于Y,使得m[y]为最小//需要执行O(n)次
将y加入X
将y从Y中删除
for 每一个(y,w):
if w属于Y and m[y]+length[y,w] < m[w]://如果新加入的点能使X中的点到w的距离更近
m[w] = m[y]+length[y,w]//m[w]储存的是距离w最近的距离长度
令y属于Y,使得m[y]为最小的过程需要执行O(n)次,故其所需的全部时间为O(N^2)。for 每一个(y,w),其对于所有节点,所需的时间为2m次(因为每条边都被考虑两次),即O(m)。故算法的时间复杂度为O( N 2 N^2 N2)。
Kruskal算法
三、文件压缩(File Compression)
版权声明:本文标题:算法设计技巧与分析(五):贪心算法(The Greedy Approach) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1729578833a1207354.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论