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

文库首页课程资源C/C++贪心算法的原理及其应用分析

贪心算法的原理及其应用分析

贪心算法

算法设计

最优子结构

需积分: 49 20 下载量 57 浏览量 2011-08-31 18:29:35 上传评论 1 收藏 981KB PPT 举报

温馨提示

试读

36页

讲解了贪心算法的基本思想及其应用，最重要的是有很多经典的实例可供参考学习

资源推荐

资源详情

资源评论

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

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

题

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

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

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

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

例题

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

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

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

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

问题的整体最优解中

包含着它的子问题的

最优解 .

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

[ 常见应用 ]

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

4.1 基本思想

用以求解最优化问题

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

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

若 i 与

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

4.2. 活动安排问题

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

内只允许一个活动使用该资源 . 设活动

的起止时间区间 [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,

活动安排问题贪心算法

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 的输入

优化函数 :

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



1





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个工作日内问题未解决可申请退款~

sdjnytzxh

粉丝: 0
资源: 7

上传资源快速赚钱

我的内容管理展开

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

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

贪心算法的原理及其应用分析

贪心算法讲解

贪婪算法的研究和应用123

贪心算法（原理和实现）

理解和掌握贪婪算法的基本思想

关于排课系统的贪心算法

贪心算法的例子——删除数字问题

贪心算法的分析与讲解

贪心算法的应用

贪心算法分析

算法学习：贪心算法的应用

算法设计与分析贪心

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

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

算法作业-贪心算法论文含实例

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

贪心算法的分析与实际应用.doc

贪心算法算法分析设计

贪心算法 算法分析与设计

贪心算法（算法分析与设计）

贪心算法的数学原理(pdf)

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

贪心算法实验报告

用贪心算法解单源最短路径问题

基于贪心算法NFA的实现 编译原理 课程设计

算法分析与设计 贪心算法

贪心算法的应用.pdf

贪心算法的应用.docx

最新资源

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

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

贪心算法算法分析与设计

基于贪心算法NFA的实现编译原理课程设计

算法分析与设计贪心算法