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

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 求解 01 背包问题算法研究 摘要：本文主要概述了求解 0-1 背包问题的两大类算法：精确算法和近 似算法，并分析了这些算法的优缺点， 并提出了求解该问题的算法发展趋势。 中国论文网 /3/view-12950243.htm 关键词：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： -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 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 Dantzig1在 20 世纪 50 年代首 次提出了背包问题（Knapsack problem，简称 KP） ，在文献2中，阐 述了该问题是一个 NP-难问题，在背包 问题中，我们很难设计出多项式时间算 法，除非 P=NP。0-1 背包问题就是，给 定一个容量为的背包和件具有价值的物 品，在不超过背包容量的前提下，选择 若干物品放入背包，使得装入背包的物 品总价值最大。同时给出一种放置物品 的方案。 背包问题就有普遍的应用背景， 在日常的许多实践中如：材料切割、资 源有效分配问题、资金估算的问题、运 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 输过程的货仓装载等起着很大的作用， 许多的组合优化问题都可以简化为背包 问题，背包问题的各种解法也可用来解 决组合优化问题，因此对 0-1 背包问题 的解法进行深入的研究具有重大的意义。 一、0-1 背包问题数学模型 在组合优化领域中，背包问题是 一个典型的 NP-难问题。在材料切割、 资源有效分配问题、资金估算的问题、 运输过程的货仓装载等领域有重大的作 用。0-1 背包问题可以描述为：给定一 个容量为 C 的背包和 n 件物品，物品 i 的重量为 wi，价值为 pi，0-1 背包问题 的数学模型可以转化为： 模型中，xi 为 0-1 变量，当物品 被选入背包时，xi=1，否则，物品没被 选如背包，xi=0。 背包问题引起了很多学者的不断 探究，目前，求解 0-1 背包问题的算法 大致上可以分为精确算法和近似算法两 大类，其中枚举法、分支定界法、回溯 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 法、图论法、动态规划法等属于精确算 法，这些算法的时间复杂度都偏大，导 致其实用性受到限制。近似算法有贪婪 算法、模拟退火算法、遗传算法、蚂蚁 算法等，虽然近似算法在时间上占有优 势，但是该算法只能够得到问题的近似 解，解的质量大幅度下降。本文将针对 字殖玫0-1 背包问题的解法进行 阐述。 二、求解 0-1 背包问题常用算法 研究 （一）求解 0-1 背包问题的精确 算法 1.枚举法 枚举法也称为穷举法，该算法的 基本思路是，针对具体问题特性，首先 将该问题的所有可行解一一列举出来， 同时在穷举的过程中，验证每个可行解 是否为问题的最优解，若是，我们就保 留该解，否则遗弃它。 用枚举法解决 0-1 背包问题，首 先，我们必须一一列举出件物品全部的 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 子集，再寻找全部可行的子集（物品总 重量不超出背包本身所能承受重量的子 集） ，然后对这些子集进行验证，计算 出各个可行子集的总重量以及对应的价 值和，分析比较求出价值最大的子集。 用枚举法求解 0-1 背包问题，首先需要 穷举出所有可行解，然后在判断是否为 最优解，算法最后一定可以得到全局最 优解。对于有 n 件物品的背包问题，不 管产生子集的计算方法的效率有多高， 枚举法始终会造成一个 O（2n）的算法， 当 n 很大时，显然该方法的时间复杂度 太大。 2.回溯法 回溯法又称为试探法，它是一种 按照深度优先策略进行系统地搜索问题 最优解的方法。回溯法的基本思想是， 对于给定问题，先定义解空间以及解空 间的结构（典型的结构是树或图） ，然 后解空间状态树中从根节点出发按照深 度优先策略进行搜索。在搜索至任意结 点时，总是先进行判断，该结点是否包 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 含问题的可行解，若包含问题的可行解 就继续进入该子树搜索，否则，进行相 应的剪枝。按照此方法逐层向上回溯， 直到搜索完整个解空间，找到问题的最 优解。 用回溯法求解 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）搜索解空间：从根节点利 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 用深度优先策略来搜索状态空间树，只 要左节点是可行解就一直沿着左节点向 下搜索，对于右节点，定义界限函数判 断右子树是否包含问题的最优解，从而 实行相应的剪枝，避免无效搜索，重复 此步骤，直到空间状态树被搜索完，找 到问题的最优解。 回溯法在解决 0-1 背包问题时， 利用深度优先的策略进行搜索解空间树， 在左子树是可行的情况下，一直进入左 子树搜索，否则考虑右子树搜索，定义 了界限函数，只有右子树满足该界限函 数，即可能包含最优解时才进入右子树 进行搜索，否则进行剪枝，这样大大减 少了节点的个数，加快了搜索速度。但 是，在糟糕的情况下，有 O（2n）个右 子树结点需要计算界限函数，由于界限 函数的时间复杂度是 O（n） ，因此回溯 法求解 0-1 背包问题时间复杂度为 O（n2n ） 。 3.动态规划 20 世纪 50 年代，动态规划算法 首次由 R.E.Bellman 等提出，它是一种 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 8 将多阶段决策转化为单阶段决策求解问 题的办法。基本步骤是： （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 背包问题满足最优子结构的性质， 建立如下状态转移方程： -精选财经经济类资料- -最新财经经济资料-感谢阅读- 9 动态规划是求解 0-1 背包问题的 一种常用算法，算法的原理以及思路清 楚明了，实施起来比较简单。算法的时 间复杂度为 O（nC） ，但是在规模较大 的问题上动态规划算法并不理想，它在 求解规划较大的背包问题上还是存在着 困难，针对动态规划算法的也出现了一 些改进算法，文献3他们通过改进动态 规划算法的状态表示从而减少状态个数 的计算，以此提高算法的时间效率。 （二）求解 0-1 背包问题的近似 算法 1.贪婪算法 贪婪算法是一种启发式算法，采 用自顶向下的迭代方法相继做出贪心选 择。算法在迭代过程中的每一步选择在 当前状态看来是最优的选择，却没有从 全局最优考虑。该算法试图通过每步的 局部最优得到全局最优解。但是该算法 并不总能够得到问题的最优解。 选取价值最大者、选取重量最小 者、选取单位价值最大者（价值密度最 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 10 大者）是求解 0-1 背包问题常用的三种 贪心策略。本文采用价值密度（价值重 量比）最大的贪婪策略，求解 0-1 背 包问题的过程如下： 分别求出给定的 n 件物品的价 值密度（价值重量比） ， 按照 n 件物品的价值密度，进 行降序排列 从价值密度最大的物品开始， 按照步骤中物品的排序依次做出贪心 选择，若当前物品的重量小于背包剩余 的容量，则将该物品放入背包，并对该 物品进行标记（表明已经被选中放入包 中） ，重复该步E ，直到物品的重量大 于背包剩余的容量无法再装入物品为止。 贪婪算法在第二步将物品按照价 值密度大小进行降序排列花费了主要的 时间，因此贪心算法的时间复杂度为 O（nlogn） 。 2.模拟退火算法 模拟退火（Simulated -精选财经经济类资料- -最新财经经济资料-感谢阅读- 11 Annealing，SA）是一种基于蒙特卡罗 迭代求解策略的启发式随机寻优算法， 它来源于固体退火原理，从某个较高的 初始温度出发，随着温度参数的不断下 降，同时，结合概率突跳特性，在解空 间中随机寻找目标函数的全局最优解， 即使处于局部最优解，也能够概率性地 跳出并最终收敛到全局最优解。 模拟退火算法求解 0-1 背包问题 的步骤： （1）构建 0-1 背包问题的解空 间，选择算法迭代初始解。0-1 背包问 题的解空间，因为初始解对算法最终所 得的结果影响不大，一般我们选择 （0，0，0）为初始解。 （2）新解的构造。构造新解一 般有三种情况，随机选取物品 i，若 不在背包中则将其装入；随机选取物 品 i，若不在背包中将其放入，同时从 背包中随机取出物品 j；随机选取物 品 i，若在包中则将其取出，同时随机 放入物品 j。 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 12 （3）针对新解的构造计算目标 函数差（背包的价值差）和重量差。目 标函数差为： 相应的背包的重量差： （4）接受策略。该算法采用了 扩充的蒙特卡洛准则： 其中为当前状态下背包重量，为 温度控制参数。 模拟退火算法中的温度控制参数 控制着优化方向，向目标逼近，同时以 概率来接收劣质解，有效的避免陷入局 部最优，从而最终趋于全局最优解。 3.遗传算法 遗传算法是借鉴生物进化法则而 形成的一种自适应全局化概率搜索算法。 它从初始种群开始，经过选择、交叉、 变异操作生成新的种群，由此更新种群 直到满足终止条件，从而完成最优解的 自适应搜索。一般计算步骤如下： 从上面的算法流程，我们可以看 出遗传算法是从串集而不是单个初始解 开始迭代求最优解，因此搜索覆盖面积 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 13 大，利于全局最优解的获得，同时，算 法采用传统的二进制编码，仅用适应度 函数评估个体等这使得遗传算法实现比 较简单。但是遗传算法存在过早收敛、 算法精度、可行性缺乏定量分析方法， 进化后期多样性降低等问题；随着背包 规模的扩大，常因陷入局部最优解使得 求解质量不高。 三、求解 0-1 背包问题的其他算 法以及改进算法 除了上面介绍的几种算法外，求 解 0-1 背包问题的算法还有许多如：蚁 群算法、粒子群优化算法、禁忌搜索算 法、演化算法4、二进制狼群算法5 、 DNA 算法等。 目前，通过结合各算法的优缺点 出现了许多混合算法。文献6中，将贪 婪法和遗传法结合提出了改进的排挤遗 传算法。文献7将模拟退火思想引入遗 传算法，有效的克服了遗传算法易于陷 入局部最优解的缺点。在文献8中将粒 子群优化算法中引入粒子速度权重值自 -精选财经经济类资料- -最新财经经济资料-感