数字执本与率用
背包问题求解算法研究
黄林峰
(淄博职业学院信息工程系山东淄博255314)
算法分析
摘要:01背包问题(KnapsackProblem)是运筹季中一个经典的NP难问题,达意味着肾包同题不存在多项式时间算法,但大部分问题存在伪多项式算法,加何我到最有效的算法以解决不同情况下的问题一直是研究人页研究的地方。因此,研究背包问题不论是对算法及复杂性理论研究,还是解决现实问题，部有非常大的积极意义
关键词：肯包问题启发式算法遗传算法
中图分类号：TP181 1背包问题简介
文献标识码：A
01背包间题(KnapsackProblem)是运筹学中一个经典的NP难问题，该问题的一般语言描述是：现有=1-n)个物品和一个可以容纳M重量的背包，每个物品有一个效益v和一个重量Wj，将x物品放人背包将消耗Wx的重量且得到Vx的效益，并且物品要么装要么不装，采用怎样的策略装包才能使装入的总效益值最大且不违反约束？
显然，由于背包容量M的限制，装人包中物品总重量不能超过 M。如果这些物品的重量之和小于M，则将这些物品都装人将获得最大效益。本文假设物品重量之和大于M，且每个物品的重量不超过 M，不然可直接去掉该物品，得到的问题和原问题是一样的。
Mex
MAX
s.t.
Za,x,sb
(1)(2)
X, E (0.1)
(3)
其中n为物品总数，a和c,为第1个物品的重量和价值，b为背包的容量
我们称上述问题为KP问题，也即单约束的01背包问题，它是最简单的01背包问题。KP问题是所有01背包问题的原型，由该问题可以衍生多种更复杂的背包问题，如多背包问题，有限背包问题等。
背包问题有广泛的运用背录。现实中经常会出现这种情况，某部门要完成一项工程，该工程有很多独立的模块，现有Ⅱ个人可以承担这些模块，由于各个人专长不同，完成不同的模块所需要的时间也不同，且让不同的人完成不同的模块需要支付的薪水也不同，于是产生了这样一个问间题：在总开支的约束下，指派哪个人完成哪个模块会使得完成的效率最高(总时闻最少)。这个问题就是MCKP间题，一个人相当一组，每个人能完成的模块相当于这一组中可供选择的物品，完成不同模块需要支付的薪水相当于选择不同物品时消
开始
初始种群
重组
适虚度计算选择形成下一代种判断终止
结来
图1进化算法基本框架
收移日期：2015-11-09
文章编号：1007-9416(2015)12-0135-0)
耗的资源，完成不同的模块需要的时闻就是创造的价值，而总开支就是总约束，间题的目标函数就是使完成工程的时间最短。问题求解在一维约束下的最小值，当然，如果对目标函数取反就成了 MCKP间题。
2背包问题研究现状
Dantizig于五十年代提出背包问题后，背包问题一直被广泛地研究。早期的研究重点主要是KP问题。到八十年代时，KP问题的解已趋完美，很多算法能在较短时间内得到高质量的解，研究重点转向MKP，MMKP以及其他由KP间题衍生的背包问题，MKP问题的精确算法主要集中在分枝限界上，这类方法通常需要得到问题的一个近似界，于是多种松弛问题被提出。由于精确算法求解背包问题花费的时间通常很长，因此近似算法得以大量应用。MKP的近似算法主要集中在混合启发式算法上，这些算法会利用多种与问题有关的性质来启发求解，目前，启发式求解MKP问题的算法能够得到间题很好地解，九十年代后，伤生算法被引人用于解决背包问题，仿生算法是计算机模拟自然界生物行为的算法，如遗传算法(GA)，蚊群算法，粒子群优化算法(PSO),这类算法在求解背包间题时表现出较好性能。
本文在对背包问题调研时，研究了很多不同的启发式方法，这些方法千差万别，但都被称为启发式方法，这种命名方式无法反映算法的特点，目前还没有资料给出一个大概的分类。有鉴于此，本文根据这些算法的特点，将这些启发式算法分为两类：确定性启发算法和不确定启发算法。
确定性启发算法是指对同一间题多次求解结果不变的算法，这类算法的流程是确定的，没有随机性，对同一间题的计算过程是完全一样的。贪心法，基于动态规划的启发式方法等传统算法都是这类算法。
不确定启发算法是指对同一个问题运行多次产生的解不同的算法，这类算法会引入随机决策，因而在搜索解时只是给出了求解的一个大概方向，面不是确定的决策序列。这类算法包括进化算法，蚁群算法，粒子群优化算法等。进化算法提供了求解问题的通用框
架，如图1所示： 3结语
背包问题是NP难问题，这意味着背包问题不存在多项式时间算法，但大部分问题存在伪多项式算法，如何找到最有效的算法以解决不同情况下的间题一直是研究人员研究的地方。因此，研究背包问题不论是对算法及复杂性理论研究，还是解决现实问题，都有
非常大的积极意义。参考文献
[1 JDeb K. Muiti120bjective Optimization Using Evolutionary Algorithms. Chicester, UK:Johnwiley & Sons, 2001
[2]P.C. Chu; J.E. Beasley. A Genetic Algorithm for the Muitidi-mensiona1 Knapsack Problem,Jourma1 of Heuristics,1998,4,PP: 63-86.
作者简介：黄林峰(1981一),男,汉族,山东烟台人,毕业于中国科技大学,现就职于满博职业学院,研究生,制教投,研究方向：进化计算、智能
信息处理等。
135