利用贪心算法解背包问题.doc_贪心算法解背包问题资源-CSDN文库

需积分: 11 57 浏览量 2010-11-16 08:47:20 上传评论收藏 42KB DOC 举报

资源推荐

资源详情

资源评论

[转]利用贪心算法解背包问题

算法贪心背包算法 贪心背包

一、贪心算法介绍

贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上

加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对

所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优

解。如图的单源最短路径、最小生成树问题等。在一些情况下，即使贪心算法

不能得到整体最优解，但其最终结果却是最优解的很好近似解。

贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性

质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解

的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心

算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解

时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态

规划算法或贪心算法求解的关键特征。

贪心算法与动态规划算法的差异，将通过下面的利用贪心算法求解背包问题来

说明。

二、背包问题

【问题描述】：先来看看  背包问题的描述：给定  种物品和一背包。物品 

的重量是 ，其价值为 ，背包容量为 。问应如何选择装入背包中的物品，

使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品 

只有两种选择，即装入背包或不装入背包。不能将物品  装入背包多次，也不

能只装入部分的物品 。背包问题与  背包问题类似，所不同的是在选择物

品  装入背包时，可以选择物品  的一部分，而不一定要全部装入背

包，。

【算法分析】：这两类问题都具有最优子结构性质。对于  背包问题，设 

是能装入容量为  的背包的具有最大价值的物品集合，则 是 个

物品  可装入容量为  的背包的具有最大价值的物品集

合。对于背包问题，类似地，若它的一个最优解包含物品 ，则从该最优解中

拿出所含的物品  的那部分重量 ，剩余的将是  个原重物品 

 及重为  的物品  中可装入容量为  的背包且具有最大价值

的物品。

虽然这两个问题极为相似，但背包问题可以用贪心算法求解，而  背包问题

却不能用贪心算法求解。用贪心算法求解背包问题的步骤是，首先计算每种物

品单位重量的价值 ；然后，依贪心选择策略，将尽可能多的单位重量价

值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未

超过 ，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一

直进行下去，直到背包装满为止。

【算法实现】 算法的 实现如下：

其中背包信息从文件中读取，点击进入该文件下载界面



 !"#$%&'$(%

) !#$*$+,,物品的数量

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

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

内容反馈

ncsilent

粉丝: 8
资源: 10

最新资源

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

feedback-tip