求解0—1背包问题算法研究

摘要：本文主要概述了求解0-1背包问题的两大类算法：精确算法和近似算法，并分析了这些算法的优缺点，并提出了求解该问题的算法发展趋势。

关键词：0-1背包问题；精确算法；近似算法

中图分类号：TP312 文献识别码：A 文章编号：1001-828X（2017）010-0-03

The Study of the 0-1 Knapsack Problem Algorithm

Abstract： This paper mainly summarizes the solving 0-1 knapsack problem algorithm of two categories： accurate and approximate algorithms， and analyzes the advantages and disadvantages of these algorithms， and put forward the development trend of algorithms to solve the problem.

Keywords： 0-1 knapsack problem， precise algorithm， approximate algorithm

Dantzig[1]在20世纪50年代首次提出了背包问题（Knapsack problem，简称KP），在文献[2]中，阐述了该问题是一个NP-难问题，在背包问题中，我们很难设计出多项式时间算法，除非P=NP。0-1背包问题就是，给定一个容量为的背包和件具有价值的物品，在不超过背包容量的前提下，选择若干物品放入背包，使得装入背包的物品总价值最大。同时给出一种放置物品的方案。

背包问题就有普遍的应用背景，在日常的许多实践中如：材料切割、资源有效分配问题、资金估算的问题、运输过程的货仓装载等起着很大的作用，许多的组合优化问题都可以简化为背包问题，背包问题的各种解法也可用来解决组合优化问题，因此对0-1背包问题的解法进行深入的研究具有重大的意义。

一、0-1背包问题数学模型

在组合优化领域中，背包问题是一个典型的NP-难问题。在材料切割、资源有效分配问题、资金估算的问题、运输过程的货仓装载等领域有重大的作用。0-1背包问题可以描述为：给定一个容量为C的背包和n件物品，物品i的重量为wi，价值为pi，0-1背包问题的数学模型可以转化为：

模型中，xi为0-1变量，当物品被选入背包时，xi=1，否则，物品没被选如背包，xi=0。

背包问题引起了很多学者的不断探究，目前，求解0-1背包问题的算法大致上可以分为精确算法和近似算法两大类，其中枚举法、分支定界法、回溯法、图论法、动态规划法等属于精确算法，这些算法的时间复杂度都偏大，导致其实用性受到限制。近似算法有贪婪算法、模拟退火算法、遗传算法、蚂蚁算法等，虽然近似算法在时间上占有优势，但是该算法只能够得到问题的近似解，解的质量大幅度下降。本文将针对幾种常用的0-1背包问题的解法进行阐述。

二、求解0-1背包问题常用算法研究

（一）求解0-1背包问题的精确算法

1.枚举法

枚举法也称为穷举法，该算法的基本思路是，针对具体问题特性，首先将该问题的所有可行解一一列举出来，同时在穷举的过程中，验证每个可行解是否为问题的最优解，若是，我们就保留该解，否则遗弃它。

用枚举法解决0-1背包问题，首先，我们必须一一列举出件物品全部的子集，再寻找全部可行的子集（物品总重量不超出背包本身所能承受重量的子集），然后对这些子集进行验证，计算出各个可行子集的总重量以及对应的价值和，分析比较求出价值最大的子集。用枚举法求解0-1背包问题，首先需要穷举出所有可行解，然后在判断是否为最优解，算法最后一定可以得到全局最优解。对于有n件物品的背包问题，不管产生子集的计算方法的效率有多高，枚举法始终会造成一个O（2n）的算法，当n很大时，显然该方法的时间复杂度太大。

2.回溯法

回溯法又称为试探法，它是一种按照深度优先策略进行系统地搜索问题最优解的方法。回溯法的基本思想是，对于给定问题，先定义解空间以及解空间的结构（典型的结构是树或图），然后解空间状态树中从根节点出发按照深度优先策略进行搜索。在搜索至任意结点时，总是先进行判断，该结点是否包含问题的可行解，若包含问题的可行解就继续进入该子树搜索，否则，进行相应的剪枝。按照此方法逐层向上回溯，直到搜索完整个解空间，找到问题的最优解。

用回溯法求解0-1背包问题的一般步骤：

（1）定义解空间：0-1背包问题的解可以用n维的向量X={（x1，x2，…，xn）|xi=0或1，i=1，2，…，n}来表示，其中每个分量xi是一个0-1决策变量，xi=1就表示第i件物品被装入背包，否则xi=2就表示第件物品不被装入背包。

（2）确定解空间的结构：对于给定的n件物品，我们有序的考虑每个物品是否被选入背包中，以便枚举出全部的状况，从而可以用一颗高度为n的完全二叉树（如图一）来表示背包问题的解空间，从根节点到叶子的每一条路径就对应解空间的一个解向量。

（3）搜索解空间：从根节点利用深度优先策略来搜索状态空间树，只要左节点是可行解就一直沿着左节点向下搜索，对于右节点，定义界限函数判断右子树是否包含问题的最优解，从而实行相应的剪枝，避免无效搜索，重复此步骤，直到空间状态树被搜索完，找到问题的最优解。

回溯法在解决0-1背包问题时，利用深度优先的策略进行搜索解空间树，在左子树是可行的情况下，一直进入左子树搜索，否则考虑右子树搜索，定义了界限函数，只有右子树满足该界限函数，即可能包含最优解时才进入右子树进行搜索，否则进行剪枝，这样大大减少了节点的个数，加快了搜索速度。但是，在糟糕的情况下，有O（2n）个右子树结点需要计算界限函数，由于界限函数的时间复杂度是O（n），因此回溯法求解0-1背包问题时间复杂度为O（n×2n）。

3.动态规划

20世纪50年代，动态规划算法首次由R.E.Bellman等提出，它是一种将多阶段决策转化为单阶段决策求解问题的办法。基本步骤是：

（1）寻找最优解的本质，构造它的结构特性；

（2）递归的去定义最优值；

（3）自底向上的去求最优值；

（4）依据算出来的最优值所得的信息去构造一个最优解。

如果X=（x1，x2，…，xn）是0-1背包问题的最优解，则（x1，x2，…，xn）是子问题：，的最优解。0-1背包问题具有最优化原理，因此该问题可以用动态规划来求解。

动态规划法求解0-1背包问题的一般步骤：

（1）建立规划模型：设子问题是m（i，j），它表示前个物品放到背包容量为时所能获得的最大价值。

（2）初始化迭代条件：

（3）建立状态转移方程：根据0-1背包问题满足最优子结构的性质，建立如下状态转移方程：

动态规划是求解0-1背包问题的一种常用算法，算法的原理以及思路清楚明了，实施起来比较简单。算法的时间复杂度为O（nC），但是在规模较大的问题上动态规划算法并不理想，它在求解规划较大的背包问题上还是存在着困难，针对动态规划算法的也出现了一些改进算法，文献[3]他们通过改进动态规划算法的状态表示从而减少状态个数的计算，以此提高算法的时间效率。

（二）求解0-1背包问题的近似算法

1.贪婪算法

贪婪算法是一种启发式算法，采用自顶向下的迭代方法相继做出贪心选择。算法在迭代过程中的每一步选择在当前状态看来是最优的选择，却没有从全局最优考虑。该算法试图通过每步的局部最优得到全局最优解。但是该算法并不总能够得到问题的最优解。

选取价值最大者、选取重量最小者、选取单位价值最大者（价值密度最大者）是求解0-1背包问题常用的三种贪心策略。本文采用价值密度（价值重量比）最大的贪婪策略，求解 0-1 背包问题的过程如下：

①分别求出给定的n件物品的价值密度（价值重量比），

②按照n件物品的价值密度，进行降序排列

③从价值密度最大的物品开始，按照步骤②中物品的排序依次做出贪心选择，若当前物品的重量小于背包剩余的容量，则将该物品放入背包，并对该物品进行标记（表明已经被选中放入包中），重复该步驟，直到物品的重量大于背包剩余的容量无法再装入物品为止。

贪婪算法在第二步将物品按照价值密度大小进行降序排列花费了主要的时间，因此贪心算法的时间复杂度为O（nlogn）。

2.模拟退火算法

模拟退火（Simulated Annealing，SA）是一种基于蒙特卡罗迭代求解策略的启发式随机寻优算法，它来源于固体退火原理，从某个较高的初始温度出发，随着温度参数的不断下降，同时，结合概率突跳特性，在解空间中随机寻找目标函数的全局最优解，即使处于局部最优解，也能够概率性地跳出并最终收敛到全局最优解。

模拟退火算法求解0-1背包问题的步骤：

（1）构建0-1背包问题的解空间，选择算法迭代初始解。0-1背包问题的解空间，因为初始解对算法最终所得的结果影响不大，一般我们选择（0，0，…，0）为初始解。

（2）新解的构造。构造新解一般有三种情况，①随机选取物品i，若不在背包中则将其装入；②随机选取物品i，若不在背包中将其放入，同时从背包中随机取出物品j；③随机选取物品i，若在包中则将其取出，同时随机放入物品j。

（3）针对新解的构造计算目标函数差（背包的价值差）和重量差。目标函数差为：

相应的背包的重量差：

（4）接受策略。该算法采用了扩充的蒙特卡洛准则：

其中为当前状态下背包重量，为温度控制参数。

模拟退火算法中的温度控制参数控制着优化方向，向目标逼近，同时以概率来接收劣质解，有效的避免陷入局部最优，从而最终趋于全局最优解。

3.遗传算法

遗传算法是借鉴生物进化法则而形成的一种自适应全局化概率搜索算法。它从初始种群开始，经过选择、交叉、变异操作生成新的种群，由此更新种群直到满足终止条件，从而完成最优解的自适应搜索。一般计算步骤如下：

从上面的算法流程，我们可以看出遗传算法是从串集而不是单个初始解开始迭代求最优解，因此搜索覆盖面积大，利于全局最优解的获得，同时，算法采用传统的二进制编码，仅用适应度函数评估个体等这使得遗传算法实现比较简单。但是遗传算法存在过早收敛、算法精度、可行性缺乏定量分析方法，进化后期多样性降低等问题；随着背包规模的扩大，常因陷入局部最优解使得求解质量不高。

三、求解0-1背包问题的其他算法以及改进算法

除了上面介绍的几种算法外，求解0-1背包问题的算法还有许多如：蚁群算法、粒子群优化算法、禁忌搜索算法、演化算法[4]、二进制狼群算法[5]、DNA算法等。

目前，通过结合各算法的优缺点出现了许多混合算法。文献[6]中，将贪婪法和遗传法结合提出了改进的排挤遗传算法。文献[7]将模拟退火思想引入遗传算法，有效的克服了遗传算法易于陷入局部最优解的缺点。在文献[8]中将粒子群优化算法中引入粒子速度权重值自适应调整策略，有效的改进了算法的搜索能力差、收敛速度慢等问题。

四、结语

从本文的阐述我们可以看出，尽管求解0-1背包问题的算法有很多，但是若背包问题规模过大的话，这些算法在时间或空间的复杂度上还是相当大的，应用起来还存在着一定的局限性。所以我们需要对现有的算法进行理论上更深刻的研究，从而对算法进行改进与完善。同时继续研究多种算法的混合优化算法，结合其他学科，提出新的更优算法。而我们也可以从对背包问题解法的研究中得到更多的启发，从而能更好的理解其它组合优化问题的解法，推动组合最优化问题的解法研究。

参考文献：

[1]G.B.Danztig. Dsiceret Variable Extremum Problems[J]. Operations Research， 1957 （5）： 266-277.

[2]M R Garey， D S Johnson. Computers and Intractability： A Guide to the Theory of NP-Completeness[J]. San Francisco： W H Freeman and Co， 1979.

[3]蓝雯飞，吴子莹，杨波.背包问题的动态规划改进算法[J].中南民族大学学报：自然科学版，2016，32（4）：101-105.

[4]王熙照，贺毅朝.求解背包问题的演化算法[J].软件学报，2017，28（1）：1-16.

[5]吴虎胜，张凤鸣，战仁军，汪送，张超.求解0-1背包问题的二进制狼群算法[J].系统工程与电子系统，2014，36（8）：1660-1666.

[6]刘文涛，胡家宝.求解 0-1 背包问题的改进排挤遗传算法[J].计算机工程与设计， 2011，32（6）.

[7]张盛意，蔡之华，占志刚.基于改进模拟退火的遗传算法求解 0-1 背包问题[J]. 微电子学与计算机，2011，28（2）：61-64.

[8]蔡敏.背包问题求解的建模及性能分析[J].内蒙古师范大学学报：自然科学汉文版，2016，45（1），13-16.

作者简介：田秀芹（1988-），女，河南鹿邑人，助教，理学硕士，主要从事稀疏优化研究。

基金项目：2017年度广西高校中青年教师基础能力提升项目，项目编号：2017KY0712。