Matlab中贪婪算法求解背包问题的研究与应用

晏 杰

（武夷学院，福建 武夷山 354300）

Matlab中贪婪算法求解背包问题的研究与应用

晏 杰

（武夷学院，福建 武夷山 354300）

本文对贪婪算法进行了分析，总结了贪婪算法解决问题的思路，根据改进的贪婪算法解决策略，通过Matlab对贪婪算法在背包问题中的应用进行了具体实现和详细的分析.

Matlab；贪婪算法；背包；研究与应用

1 引言

为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法.贪婪算法主要用于设计数值最优化问题的算法，它是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题能产生整体最优解或者整体最优解的近似解.算法容易实现也易于理解，这使得算法在编码和执行的过程中都有着一定的速度优势，同时也提高了效率并节省了时间.

2 贪婪算法概述

2.1 贪婪算法的定义

贪婪算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略.

2.2 贪婪算法思想

贪婪算法采用逐步构造最优解的方法，即在每个阶段，都选择一个看上去最优的策略（在一定的标准下）.策略一旦选择就不可再更改，贪婪决策的依据称为贪婪准则，也就是从问题的某一个初始解出发并逐步逼近给定的目标，以尽可能快的要求得到更好的解.而且它在设计时没有固定的框架，关键在于贪婪策略的选择.但要注意的是选择的贪婪策略要具有无后向性，即某阶段状态一旦确定下来后，不受这个状态以后的决策的影响，也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关.

2.3 贪婪算法的特性

贪婪算法及贪婪算法可解决的问题通常大部分都有如下的特性:

（1）有一个以最优方式来解决的问题.为了构造问题的解决方案,有一个候选的对象的集合.

（2）随着算法的进行,将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象.

（3）有一个函数来检查一个候选对象的集合是否提供了问题的解答.该函数不考虑此时的解决方法是否最优.

（4）还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解.和上一个函数一样,此时不考虑解决方法的最优性.

（5）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解.

（6）最后,目标函数给出解的值.

2.4 贪婪算法解决问题的步骤

使用贪婪算法解决问题，通常需要做好以下几个方面的工作：

（1）明确问题的求解目标.

（2）分析问题所包含的约束条件.

（3）建立优化函数.

（4）制定贪婪准则.

清楚问题的求解目标、所包含的约束条件及优化函数之后，就可以着手制定一个可行的贪婪准则.贪婪准则的制定是用贪婪算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低.

3 Matlab中贪婪算法求解背包问题的具体实现

3.1 问题描述

有一组物品共有9种，给出每种物品的重量、价值、单位价值.假设背包总容量为30千克，请确定装包方案，要求所装物品总重量不超过30千克且总价值最大.具体数据如下表所示：

物品号 重量（千克） 价值（元） 单位价值9 3 300 100 2 45 45 8 4 180 45 1 4 2.5 100 40 7 5 200 40 3 30 30 5 10 150 15 6 6 90 15 1 1 2 10 5

3.2 Matlab中贪婪算法求解背包问题的关键代码

%per_value已经按降序排好，其他参数也对应排好.

3.3 求解过程

先建立greedy_beibao函数的4个参数，具体如下：

然后调用greedy_beibao函数进行求解，并得到最终结果.

3.4 运行结果

输出对应装入背包的物品号chanpin_N=928 473501.

输出装入物品后背包总重量ans=28.5000.输出装入物品后背包总价值ans=1015.

3.5 结果分析

通过程序运行的结果，我们可以看出，9种物品中除了物品6以外的8种物品都装入了背包,这时总价值最大为1015元,对应背包重量为28.5千克，装入背包的物品编号依次为：9284735 1.

4 结束语

贪婪算法的优点在于在求解问题的每一步它都是选择最优解，算法就容易实现也易于理解，这使得算法在编码和执行的过程中都有着一定的速度优势，同时也提高了效率并节省了时间.然而贪婪算法的缺点也是不容忽视的，由于它采取逐步获得最优解的方法而不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解.因此贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它都能得出整体最优解或者是整体最优解的近似解.与回溯法等比较,它的适用区域相对狭窄许多,因此正确地判断它的应用时机十分重要，不过贪婪算法的优点结合其他算法的应用将是以后研究的方向.

〔1〕王德才.基于能量分析的地震动输入选择及能量谱研究[M].合肥工业大学出版社，2010.

〔2〕刘洋.0-1 背包的遗传算法及其改进[J].天津师范大学学报（自然科学版），2003.

〔3〕肖小文.设施区位决策支持系统设计与开发[M].华东师范大学出版社，2010.

TP18

A

1673-260X（2012）09-0023-02