背包问题求解算法研究

摘要：01背包问题（Knapsack Problem）是运筹学中一个经典的NP难问题，这意味着背包问题不存在多项式时间算法，但大部分问题存在伪多项式算法，如何找到最有效的算法以解决不同情况下的问题一直是研究人员研究的地方。因此，研究背包问题不论是对算法及复杂性理论研究，还是解决现实问题，都有非常大的积极意义。

关键词：背包问题 启发式算法 遗传算法

中图分类号：TP181 文献标识码：A 文章编号：1007-9416（2015）12-0000-00

1 背包问题简介

01背包问题（Knapsack Problem）是运筹学中一个经典的NP难问题，该问题的一般语言描述是：现有j（j=1……n）个物品和一个可以容纳M重量的背包，每个物品有一个效益vj和一个重量wj，将x物品放入背包将消耗Wx的重量且得到Vx的效益，并且物品要么装要么不装。采用怎样的策略装包才能使装入的总效益值最大且不违反约束？

显然，由于背包容量M的限制，装入包中物品总重量不能超过M。如果这些物品的重量之和小于M，则将这些物品都装入将获得最大效益。本文假设物品重量之和大于M，且每个物品的重量不超过M，不然可直接去掉该物品，得到的问题和原问题是一样的。

MAX （1）

s.t. （2）

{0，1}； （3）

其中 为物品总数， 和 为第 个物品的重量和价值， 为背包的容量

我们称上述问题为KP问题，也即单约束的01背包问题，它是最简单的01背包问题。KP问题是所有01背包问题的原型，由该问题可以衍生多种更复杂的背包问题，如多背包问题，有限背包问题等。

背包问题有广泛的运用背景。现实中经常会出现这种情况，某部门要完成一项工程，该工程有很多独立的模块，现有n个人可以承担这些模块，由于各个人专长不同，完成不同的模块所需要的时间也不同，且让不同的人完成不同的模块需要支付的薪水也不同，于是产生了这样一个问题：在总开支的约束下，指派哪个人完成哪个模块会使得完成的效率最高（总时间最少）。这个问题就是MCKP问题，一个人相当一组，每个人能完成的模块相当于这一组中可供选择的物品，完成不同模块需要支付的薪水相当于选择不同物品时消耗的资源，完成不同的模块需要的时间就是创造的价值，而总开支就是总约束，问题的目标函数就是使完成工程的时间最短。问题求解在一维约束下的最小值，当然，如果对目标函数取反就成了MCKP问题。

2背包问题研究现状

Dantizig于五十年代提出背包问题后，背包问题一直被广泛地研究。早期的研究重点主要是KP问题。到八十年代时，KP问题的解已趋完美，很多算法能在较短时间内得到高质量的解，研究重点转向MKP，MMKP以及其他由KP问题衍生的背包问题。MKP问题的精确算法主要集中在分枝限界上，这类方法通常需要得到问题的一个近似界，于是多种松弛问题被提出。由于精确算法求解背包问题花费的时间通常很长，因此近似算法得以大量应用。MKP的近似算法主要集中在混合启发式算法上，这些算法会利用多种与问题有关的性质来启发求解，目前，启发式求解MKP问题的算法能够得到问题很好地解。九十年代后，仿生算法被引入用于解决背包问题，仿生算法是计算机模拟自然界生物行为的算法，如遗传算法（GA），蚁群算法，粒子群优化算法（PSO），这类算法在求解背包问题时表现出较好性能。

本文在对背包问题调研时，研究了很多不同的启发式方法，这些方法千差万别，但都被称为启发式方法，这种命名方式无法反映算法的特点，目前还没有资料给出一个大概的分类。有鉴于此，本文根据这些算法的特点，将这些启发式算法分为两类：确定性启发算法和不确定启发算法。

确定性启发算法是指对同一问题多次求解结果不变的算法，这类算法的流程是确定的，没有随机性，对同一问题的计算过程是完全一样的。贪心法，基于动态规划的启发式方法等传统算法都是这类算法。

不确定启发算法是指对同一个问题运行多次产生的解不同的算法，这类算法会引入随机决策，因而在搜索解时只是给出了求解的一个大概方向，而不是确定的决策序列。这类算法包括进化算法，蚁群算法，粒子群优化算法等。进化算法提供了求解问题的通用框架，如图1所示：

图1 进化算法基本框架

3 结语

背包问题是NP难问题，这意味着背包问题不存在多项式时间算法，但大部分问题存在伪多项式算法，如何找到最有效的算法以解决不同情况下的问题一直是研究人员研究的地方。因此，研究背包问题不论是对算法及复杂性理论研究，还是解决现实问题，都有非常大的积极意义。

参考文献

[1] Deb K. Multi2Objective Optimization Using Evolutionary Algorithms. Chicester， UK： JohnWiley & Sons， 2001

[2] P.C. Chu； J.E. Beasley. A Genetic Algorithm for the Multidimensional Knapsack Problem， Journal of Heuristics， 1998，4， PP： 63–86.

收稿日期：2015-11-09

作者简介：黄林峰（1981—），男，汉族，山东烟台人，毕业于中国科技大学，现就职于淄博职业学院，研究生，副教授，研究方向：进化计算、智能信息处理等。

推荐访问:求解 算法 背包 研究