admin 管理员组

文章数量: 1184232

文章目录

  • 贪心算法(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)

本文标签： 算法 贪心 技巧 Approach Greedy

版权声明：本文标题：算法设计技巧与分析（五）：贪心算法(The Greedy Approach) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1763631861a3256380.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。