贪心算法与动态规划的比较.docx资源-CSDN文库

版权申诉

90 浏览量 2022-05-07 17:03:00 上传评论收藏 28KB DOCX 举报

资源推荐

资源详情

资源评论

贪心算法与动态规划的比较

【摘要】介绍了计算机算法设计的两种常用算法思想：贪心算法与动态规划算法。通过

介绍两种算法思想的基本原理，比较两种算法的联系和区别。通过背包问题对比了两种算法

的使用特点和使用范围。

【关键字】动态规划；贪心算法；背包问题

1、引言

为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了

飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学

中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不

像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使

用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，

必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，

这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/ 1 背包问题进行分

析，介绍贪心算法和动态规划算法的区别。

2、背包问题的提出

给定 n 种物品( 每种物品仅有一件) 和一个背包。物品 i 的重量是 w ，其价值为 p ，

i

i

背包的容量为 M。问应如何选择物品装入背包，使得装入背包中的物品的总价值最大,每件

物品 i 的装入情况为 x ，得到的效益是 p *x 。

i

i

i

⑴部分背包问题。在选择物品时，可以将物品分割为部分装入背包，即0≤ x ≤1 ( 贪心

i

算法)。

⑵ 0/ 1 背包问题。和部分背包问题相似，但是在选择物品装入时要么不装，要么全装

入，即 x = 1 或 0。( 动态规划算法) 。

i

3、贪心算法

3.1 贪心算法的基本要素

能够使用贪心算法的许多例子都是最优化问题，每个最优化问题都包含一组限制条件和

一个优化函数，符合限制条件的问题求解方案称为可行解；使优化函数取得最佳值的可行解

称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达

到(这是贪心算法与动态规划的主要区别) 。

3.2 贪心策略的定义

贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值( 或较优解)

的一种解题方法。贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从

整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性

决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

内容反馈

版权申诉

苦茶子12138

粉丝: 1w+
资源: 6万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip