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

文库首页大数据算法与数据结构贪心算法贪心算法在最优二叉树构造中的应用以及哈夫曼编码的原理和实现

贪心算法贪心算法在最优二叉树构造中的应用以及哈夫曼编码的原理和实现

贪心算法

1 下载量 32 浏览量 2024-08-08 23:02:17 上传评论收藏 981KB PPT 举报

温馨提示

试读

36页

贪心算法，本文介绍了贪心算法在最优二叉树构造中的应用，以及哈夫曼编码的原理和实现方法。

资源推荐

资源详情

资源评论

第四章.贪心算法(Greed method)

[适用问题] 具备贪心选择和最优子结构性质的最优化问题

将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择

都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问

题会简化为一个规模更小的子问题.从而通过每一步的最

优解逐步达到整体的最优解。

例题

[算法优点]求解速度快,时间复杂性有较低的阶.

整体的最优解可通过一系列局部最优

解达到.每次的选择可以依赖以前作

出的选择,但不能依赖于后面的选择

问题的整体最优解中

包含着它的子问题的

最优解.

[算法缺点]需证明是最优解.

[常见应用]

背包问题,最小生成树,最短路径,作业调度等等

4.1 基本思想

用以求解最优化问题

算法设计与分析 > 贪心算法

[算法思路]将n个活动按结束时间非减序排列,依次考虑活动i, 若i与

已选择的活动相容,则添加此活动到相容活动子集.

4.2.活动安排问题

[问题陈述]设有n个活动E={1,2,…,n}要使用同一资源,同一时间内只

允许一个活动使用该资源. 设活动i的起止时间区间[s

, f

) ,如果选择

了活动i,则它在时间区间[s

, f

)内占用该资源;若区间[s

, f

)与[s

, f

)

不相交, 则称活动i与j是相容的. 求解目标是在所给的活动集合

中选出最大相容活动子集.

算法设计与分析 > 贪心算法

1 2 3 4 5 6 7 8 9 10 11

[例]

1 3 0 5 3 5 6 8 8 2 12

4 5 6 7 8 9 10 11 12 13 14

s[i]

f[i]

设待安排的11个活动起止时间按结束时间的非减序排列

最大相容活动子集(1, 4, 8, 11),

也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1)

活动安排问题贪心算法

template< class Type >

void GreedySelector(int n, Type s[ ], Type f[ ], bool A[] )

{ A[ 1 ] = true;

int j = 1;

//从第二个活动开始检查是否与前一个相容

for (int i=2;i< =n;i+ +) {

if (s[i]>=f[j]) {

A[i] = true;

j=i;}

else A[ i] = false;} }

T(n)=O(nlogn) (未排序时)

[算法分析] T(n)=O(n) (已排序时)

算法设计与分析 > 贪心算法

[算法证明] 算法达到最优解.

[问题描述] 输入:(x1,x2,...xn), xi=0,货箱i不装船; xi=1,货箱i装船

可行解: 满足约束条件 ≤c 的输入

优化函数:

最优解:使优化函数达到最大值的一种输入.

4.3 最优装载

算法设计与分析 > 贪心算法

[例]

设n=8，[w1，…w8]=[100, 200, 50, 90, 150, 50, 20, 80]，c=400。

所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2。货箱7, 3, 6, 8, 4, 1的

总重量为390个单位且已被装载, 剩下的装载能力为10 ,小于任意

货箱.所以得到解[x1,...x8]=[ 1, 0, 1, 1, 0, 1, 1, 1]

[算法思路] 将装船过程划为多步选择，每步装一个货箱，每次从

剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上

船或船上不能再容纳其他任何一个货箱。

最优装载的贪心算法

算法设计与分析 > 贪心算法

template < class Type >

void Loading(int x[], Type w[], Type c, int n )

{ int *t = new int [n + 1]; //t记录顺序映射

Sort(w, t, n) ; //按货箱重量排序/

for (int i = 1; i < = n; i ++) x[i] = 0;

for (int i = 1;i<= n && w[t[i]] <= c; i++) {

x[t[i]] = 1;

c-= w[t[i]];}} //调整剩余空间/

算法分析: 排序为主要算法时间,所以 T(n)=O(nlogn)

算法证明:该算法能得到最优解(反证法).

剩余35页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

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

codemami

粉丝: 1362
资源: 3270

上传资源快速赚钱

我的内容管理展开

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

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

贪心算法贪心算法在最优二叉树构造中的应用以及哈夫曼编码的原理和实现

最优二叉树应用-编码与译码

哈夫曼编码（贪心算法）报告.doc

贪心算法解哈夫曼编码问题

哈夫曼编码的贪心算法设计

哈夫曼编码算法与分析(java实现)

哈夫曼编码C++实现

用贪心算法解哈夫曼编码问题(计算机算法设计与分析)

贪心算法-哈夫曼编码

0023算法笔记——【贪心算法】哈夫曼编码问题--16页.pdf

c语言实现哈夫曼编码

哈夫曼编码（贪心算法）课堂分享.pptx

算法-理论基础- 二叉树- 哈夫曼树与哈夫曼编码（包含源程序）.rar

算法分析 哈夫曼编码

哈夫曼树压缩算法实现

哈夫曼编码 贪心算法.docx

哈夫曼树与哈夫曼编码

构造二叉树 最优二叉树 树 输出二叉树到屏幕 C# .net

哈夫曼编码

哈夫曼编码算法作业作业

哈夫曼树及哈夫曼编码数据结构实验报告

贪心算法设计及其实际应用研究

哈夫曼编码课程设计（包括报告和实现程序mfc)

贪心算法算法分析设计

C++实现哈夫曼树及哈夫曼编码.rar

哈夫曼编码PPT(2020.09.20).rar

算法设计之贪心算法ppt

良心出品构造哈夫曼树及哈夫曼编码.docx

哈夫曼算法压缩文本文档

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

最新资源

算法分析哈夫曼编码

哈夫曼编码贪心算法.docx

构造二叉树最优二叉树树输出二叉树到屏幕 C# .net

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