（应用数学专业论文）背包问题的一种新算法：降维递归算法.pdf

摘要 背包问题在项目选择、材料切割、货物装载等应用中有重要的价值。从计算 复杂性理论看，背包问题是一个经典n p 难解问题。本文对单约束线性整数规划 ( i l p ，背包问题) 的特性进行了分析，通过剪去无效变量对问题进行简化并设 计了问题的一种新算法一一降维递归算法，全文共分四章。 在一二章中介绍了背包问题的产生的背景及要用到的算法。第三章中给出了 背包问题的一些性质及关键性质的证明，并在此基础上设计了一种新算法。在第 四章中对具体问题进行了数值实验，进一步从实例上验证了该算法的可行性。 关键词：整数线性规划；背包问题；无效变量：降维递归算法 a b s t r a c t k n a p s a c kp r o b l e mh a dw i d ea p p l i c a t i o n si nal o to ff i e l d s k n a p s a c kp r o b l e mi s b e l o n g sa m o n gn p l l a r dp r o b l e m s i ta l w a y sh a db e e nah o tf i e l dp r o b l e m i nt h i s p a p e r , w ea n a l y z e ds o m ep r o p e r t yf o rt h es i n g l er e s t r i c ti n t e g e rl i n e a rp r o g r a m m i n g ( k n a p s a c kp r o b l e m ) ，c u tt h ei n v a l i d e dv a r i a b l ea n ds i m p l i f yt h ep r o b l e m d e s i g n e dan e wa l g o r i t h m r e d u c ed i m e n s i o na n dr e c u r s i v ea l g o r i t h m i ti n c l u d e s f o l l o w i n gf o rc h a p t e r s h lc h a p t e r1a n d2 ，a u t h o ri n t r o d u c e st h eb a c k g r o u n do ft h ek n a p s a c kp r o b l e m a n ds o m ea l g o r i t h m s i nc h a p t e r3w eg i v es o m ec h a r a c t e r sa n dp r o o fo ft h ep r o b l e m i nc h a p t e r4 ，a u t h o rm a k e sm a t h e m a t i c a lc h e c kf o rc o n c r e t ep r o b l e m s ，p r o v e st h e f e a s i b i l i t yo fn e wa l g o r i t h r n a n dp r o p o s et h em o d i f i e dm e t h o df o rn e wa l g o r i t h m k e yw o r d s ：i l p ；k n a p s a c kp r o b l e m ；i n v a l i d e dv a r i a b l e ；r e d u c ed i m e n s i o n a n dr e c u r s i v ea l g o r i t h m 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：彦毛! 信秆趴 签字日期：沙埤( 月厶日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：压气绉枕 签字日期：yi 年月6 日主墨菩蠢二二赡日签字日期刃伊粹g 月b 日 背包问题的一种新算法：降维递归算法 1前言 所谓的背包问题( k n a p s a c kp r o b l e m 简称k p ) 一般提法如下：设有一人带 一背包上山，给定可携带物品重量限度( 容量) 为b 。设有死种物品可供选择 其重量和效用分别用q 与q ( i - - 1 ，2 ，礼) 表示。要求确定方案使得所携带物品 效用之和最大，这就是一般背包问题。其数学模型为： ( p ) ： ma xf = 三c i x i s t 。n 汀b i = l z i2o k 取整数( = l ，2 ，死) 其中a i ，c i ，b 均为大于零的整数( 对于非整数情形可相应的化为整数情 形) 。背包问题是整数规划中一类重要问题，由d a n z i g n l 在5 0 年代末期首 次提出，近年来被广泛的研究。许多实际的优化问题都可以通过建模归结为 背包问题，如工厂里的下料问题、批量切割问题等；管理中的资源分配、资 金预算、投资决策；交通运输中的装载问题等。 基于实际问题各不相同的背景，对背包问题加以推广，可衍生出一系列 相关的优化问题。我们在这里适当的介绍几类常见的衍生问题： ( 1 ) o _ 1 背包问题( 0 1k n a p s a c kp r o b l e m ) 0 - 1 背包问题( 0 - 1k n a p s a c kp r o b l e m ) 是从有h 个物品集中选取一个 子集，在总重量不超过容量b 的前提下，使得相应的效益实现最大化。其数 学模型为： n ( p ) ： ma x f = 三c 舭 n s t a i x i b i = l 毛 o ，1 ) ，i = l ，2 ，以 硕士学位论文 其中物品f 如果被选中，则= l ，否则五= 0 ( 2 ) 多约束背包问题( m u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m ) 在许多实际问题中，对物品的选择不仅在总重量上有限制，有时对总体积有 限制。这样就产生了有多个约束的背包问题。这类问题的数学模型为： ( p ) ： m a x ，= ct z i = 1 “毛ae x ，6 ( _ ，= 1 ，2 ，肌) z i d 且取整数( i = 1 ，2 ，n ) 许多简单结构的有机组合构成了复杂结构，对简单问题的深入探索也使复杂 问题问题的解决变得相对容易阳1 。在设计解决大量的复杂组合优化问题时，背包 问题往往作为子问题出现。如一般的多约束整数规划问题，通过适当的转换分解 可化为背包问题。故背包问题的算法改进，对复杂组合的优化问题算法的改进是 十分有益的。以下约定：本文所讨论的背包问题是指一般的背包问题( 不包括 0 - 1 背包问题和多约束背包问题) 。 即属于组合最合最优化问题。一般的最优化问题( o p t i m i z a t i o np r o b l e m ) 由目标函数( o b j e c t i v ef u n c t i o n ) 和约束条件( c o n s t r a i n t s ) 两部分构成： m i n i m i z e 厂( 工) = f ( x l ，x 2 ，工。) s u b j e c tt ox = ( 工l ，x 2 ，x 玎) scx 将满足所有约束条件的解空间s 称为可行域( f e a s i b l er e g i o n ) ，可行域中 的解称为可行解( f e a s i b l es o l u t i o n ) ；将可行域中使目标最小化的解称为最优 解( 0 p t i m a ls o l u t i o n ) 。对最大化问题，可将目标函数乘以( - 1 ) ，转换为最小 化问题求解。当x 或s 为离散集合构成的结空间时，这类最优化问题称为组合最 优化问题( c o m b i n a t o r i a l0 p t i m i z a t i o np r o b l e m ) 对于背包问题，已有的求解方法可分为精确算法( 如枚举法，动态规划法， 分支定界法，图论法等指数级算法) 和近似算法们( 如贪心算法，蚂蚁算法，遗 传算法等) 两大类。精确算法的特点是，所求得的解是最优解。精确算法的时间 复杂性是指数型h 1 ( 分支定界法是0 ( 2 ”) ) 的或不确定( 动态规划算法o ( b n ) ) 这一点可用来作为检验其近似他算法的精确性。与精确算法相比，近似算法计算 复杂性都是多项式的。但就目前而言，近似算法多以领域知识确立规则，从而构 成启发式规则，其算法依赖于具体问题。 所有的背包问题都属于n p h a r d 问题n 副，这就是说我们设计出背包问题的多 2 背包问题的一种新算法：降维递归算法 项式算法的可能性非常小。也即是说对于背包问题而言，我们除了枚举出整个解 空间而外就无法求得背包问题的精确解。但是应用一些普遍适用的技术手段，我 们的枚举可以变得相对容易许多。 3 硕士学位论文 2 求解背包问题的几个算法简介 2 1 贪婪算法 贪婪算法属于一步式启发算法，即每采用一个贪婪准则便做出一个不可撤回 的决策。用贪婪算法求解背包问题的特点是每一步迭代选一物品入包，直到无法 再装。该算法没有在两个可行解之问比较选择，算法结束时得到一个可行解。 解决背包问题的可能的3 种策略： ( 1 ) 从备选对物品中选择价值最大的个体，这种方法使背包价值尽可能地 增大： ( 2 ) 从备选的物品中选择最轻的个体装入背包，使背包尽可能多装物品； ( 3 ) 选择单位价值最大的物品装入背包； 上述三种策略中第三种认为最合理。 贪婪算法的基本思想是从局部的最优出发，即：首先让作用价值最大的物品 尽可能的多放，然后再考虑作用价值次大的物品，如此反复，直至装不下任何 物品该算法的特点是：简单而快捷，特别当问题的最优解只能用穷举法得到时， 用贪婪算法是寻找问题近似解的较好算法。 下面我们用一个例子来说明该算法： 例1 ：m a xf = 5 x l + 1 2 心+ 1 3 心- t - 8 、 s t 4 五十6 娩+ 7 恐+ 9 托= 1 7 x i 0 且为整数( f = 1 ，2 ，3 ，4 ) 解：对问题的变量按序列 e j = c i t z ) ，歹= 1 ，2 ，n ) 的非增顺序进行排列 得到： m a x 厂= 1 2 x 2 + 1 3 x 3 + 5 x l + + 8 x 4 s t 6 x 2 + 7 义，3 + 4 x v + 9 彳- = 1 7 t 。且为整数( i = 1 , 2 , 3 , 4 ) 令x ：= 詈 = 2 ， 剩余的容量为 4 背包问题的一种新算法：降维递归算法 1 7 6x 2 = 5 ，其中【x 】表示不大于z 的最大整数。再令置- - i ；5l = o ， 剩余 l ，j r 气1 的容量仍然为5 ，再令x 。= i | - 1 ，剩余的容量为5 二4 1 = l ，再令 l 4 j 厂11 x = i 言i - o ，剩余的容量仍然为1 。这样就得到一1 _ 近似解 五= 1 ，置= 2 ，置= o ，置= 0 ， 其近似值为 f = 2 1 2 + 0 13 + 1 5 + 0 8 = 2 9 口 贪婪算法的求解效率非常之高，不少专家学者仍然寄希望于这种算法，力图 改进它。1 9 7 7 年r i c h a r dl o u l o u 等提出了一种新的贪婪算法，这种算法可以适 用于大型多约束背包问题， 2 2 动态规划算法 动态规划法是解决多阶段决策过程最优化的一种数学方法。1 9 5 1 年美国数 学家贝尔曼等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一 系列相互联系的单阶段问题，然后逐个加以解决，从而创建了动态规划的方法。 他的特点是解决多阶段，离散性问题。他采用最优原则( p r i n c i p l eo f o p t i m a l i t y ) 来建立用于计算机最优解的递归式。所谓最优原则不管前面的策略 如何，此后的决策必须是基于当前状态( 由上一次决策产生) 的最优决策。由于 对于有些问题的某些递归式来说并不能一定保证最优原则，因此在求解问题是有 必要对他进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最 优解的递归式之后，需要执行回溯( t r a c eb a c k ) 以构造最优解。 采用动态规划方法，可以很高效的解决许多分支定界法或贪婪算法无法解决 的问题。但是，动态规划方法也存在着不足之处：到目前为止，还没有一个统一 的标准模型可供应用。由于实际问题不同，其动态规划模型也就不同。虽然理论 上可以把某些静态规划问题转化为动态规划模型来求解，但这种转化有时将变得 十分困难，要有丰富的想象力和灵活的技巧性。 2 2 1 动态规划法的基本概念 ( 1 ) 阶段：将所给问题按时间或空间特征分解成若干互相联系的阶段，以 便按次序求解每阶段的解 ( 2 ) 状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量叫 5 硕士学位论文 状态变量，常用表示第k 阶段的状态变量，用墨表示的取值集合。动态规 划中的状态具有无后效性，即当某阶段状态给定后，在这阶段以后过程的发展不 受以前各阶段状态的影响。也就是说，当前的状态是过去历史的一个完整的总结， 过程的过去历史只能通过当前的状态去影响未来的发展。 ( 3 ) 决策和策略：各阶段的状态取定以后，就可以作出不同的决定( 或策 略) ，以确定下一阶段的状态，这种决定称为决策。常用( & ) 表示第k 阶段当状 态为的决策变量，b ( ) 表示第k 阶段从状态& 出发的允许决策集合。各阶 段的决策确定后，整个问题的决策序列就构成一个策略，用 p h ”。( s 。) ，u ：( s 2 ) ，u 。( ) ) 表示。记允许策略集合为p 。，。 ( 4 ) 状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一 阶段决策的结果。若给定了吼和u 。( s k ) ，则第k + l 阶段的状态& + 也就完全确定， 其关系可用公式表示：& + 。= t k ( s k ，) 称为状态转移方程。 ( 5 ) 指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。一个n 段决策过程，从1 到刀叫做问题的原过程，从第k 阶段到第n 阶段的过程叫原过程 的一个后部子过程。k 。( s 。，p 。，) 表示初始状态为s i ，采用策略a ，。时原过程的指 标函数值，圪。( ，p k 疗) 表示第k 阶段，状态为s k ，采用策略p k ，n 时子过程的 指标函数值。最优指标函数： 厂 ( st ) = v t ，。( st ，p ：) = o p t v 七，。( si ，pk , n ) p ep k 。 表示从第k 阶段状态瓯，采用最优策略颤，刀到过程终止时的最佳效益值。 2 2 2 动态规化问题的求解步骤 动态规划的基本方法是：由最后一个阶段的优化开始，按逆向顺序逐步向前 一阶段优化扩展，并将后一阶段的优化结果带到前一个阶段中去，依次逐步向前 递推，直至全过程的优化结束这种逆向顺序逐步向前递推的方法可简称为逆序 递推法，它是解动态规划问题中经常采用的一种方法其步骤可归纳如下： ( 1 ) 将所要解决的问题恰当地划分为若干阶段，经常是按事物发展的时间 和空间来划分不同阶段，各阶段的首尾要互相衔接； ( 2 ) 正确地选择状态变量& ，确定它在每一阶段的取值范围； ( 3 ) 对每个状态变量( k = 1 ，2 ，n ) ，找出与其对应的决策变量屯( & ) 6 背包问题的一种新算法：降维递归算法 以及允许决策集合q ( ) ； ( 4 ) 对每一状态变量& ，及对应的决策变量五( & ) 计算出本阶段的各个指 标值： ( 5 ) 正确写出状态转移方程+ = 互( ，x k ( s k ) ) ； ( 6 ) 对每一对& ，仅) 计算不同指标值d k ( s k ，五) + 正+ 。( s ) 。把这些指 标值进行比较取出最优的一个，所谓最优是根据实际问题的需要确定指标值的最 大者或最小者，即 a ( s 七) = o p t d k ( s i ，) + 五+ l ( s ) q ( s k ) 由k = n ，n 一1 ，2 ，l 将上式依次逐步递推，直至全过程的优化结束， 即可求出动态规划问题的最优策略及最优指标值。、 2 2 3 动态规划法解背包问题的一个实例 maxf = 4x l + 5 x 2 + 6 x 3 s t 3x l + 4x2 + 5 x 3 lo x f 0 且为整数，( f ；1 ，2 ，3 ) 解：用动态规划方法来解，此问题变为求f 3 ( 1 0 ) 而f 3 ( 1 0 ) = 3 ”4 m 砂a 5 x 而圳 4 x 1 + 5 x 2 + 6 x 3 ) 砷2 0 ，整数，i = 1 。2 ，3 = ，m 孕莶。 4 墨+ 5 x 2 + ( 6 x 3 ) ) 3 而+ 4 x ，s 1 0 5 工3 。 。 川卸 整敢- i = 1 2 3 = l m一5a啦x0o 6 恐+ 3 而+ 4 罂xa x l o - - 5 x s 【4 x l + 5 x 2 】) l 一5 五o 、 。 3 而， 一。 日卸，整数婶加整教f = 1 2 =max 6x 3 + f 2 ( 10 5 x 3 ) j ，= 0 ，1 。2 、 。 。 = m a x 0 + 厶( 1o ) ，6 + 厂2 ( 5 ) ，12 + ( o ) 由此看到，要计算f 3 ( 1 0 ) ，必须先计算出 ( 1 0 ) ，五( 5 ) ，a ( o ) 。而 ( 1 o ) = 3 ”4 m 工：a s l x 。一5 上， 4 x l + 5 x 2 ) x 1 2 0 ，整敦f = i 2 7 硕士学位论文 同理可得 = 哩a 。x 4 x l + ( s x 2 ) ) 3 h 1 0 一4 工， 。 。 唧2 0 。整数1 = i ，2 = 1 0 照。 5 五+ 3 嚣强而( 4 墨) ) 一4 如o 、 3 而s l o 一4 南 。 j 2 卸整数 j 1 2 d ，整披 = 例m a x ，2 5 置+ z ( 1 0 - 4 五) ) = m a x z ( 1o ) ，5 + 五( 6 ) ，10 + z ( 2 ) ) 六( 5 ) = m a x f l ( 5 ) ，5 + 石( 1 ) ) ( o ) = ( 0 ) 为了要计算出a 0 0 ) ，五( 5 ) ，a ( o ) ，必须先计算出f ( 1 0 ) ，石( 6 ) ，彳( 5 ) ，彳( 2 ) ， f , o ) ，工( 0 ) 。一般地有 石( 6 ) = m a ) 【( 4 x 1 ) = 4 ( 不超过6 3 的最大整麴= 4 x b 3 3 x r b 咱o ，整数 相应的最优决策为五= b 3 】。于是得到 z o o ) = 1 2 ，f ( 6 ) = 8 ，z ( 5 ) = 4 f ( 2 ) = 0 ，z ( 1 ) = 0 ，z ( 0 ) = 0 从而 a ( i o ) = m a x f 。( 1 0 ) ，5 + z ( 6 ) ，l o + z ( 2 ) ) = m a x 1 2 ，5 + 8 ，1 0 + 0 = 1 3 同理 正( 5 ) = 5 ，五( o ) = o ，正( o ) = 0 故最后得到 a o o ) = m a x o + l ( 1 0 ) ，6 + f 2 ( 5 ) ，1 2 + 正( 0 ) = m a x 1 3 ，6 + 5 ，1 2 + 0 = 1 3 所以，最优装入方案为z = 2 ，z = 1 ，= 0 ，最大效用为1 3 s 口 背包问题的一种新算法：降维递归算法 2 3 分枝定界法 分枝定界法嘲( b r a n c ha n db o u n dm e t h o d ) 是求解整数规划常用的一种方法， 它具有灵活且便于用计算机求解等优点。它的一般思想是利用连续的( 线性规划) 模型来求解非连续的( 整数规划) 问题。 假定 是一个有取整约束的变量，而其最优连续值工：是非整数；那么在【】 ( 表示的取整值) 和【 + l 之间不可能包括任何可行整数解。因此，以的可 行整数值必然满足& x ：】+ 1 之一。把这两个条件分别加到原线性规 划的解空间上，产生两个互斥的线性规划子问题。实际上这一过程利用了整数约 束条件，在“分割时删除了不包含可行整数点的部分连续空间 ( 石：】 以 x ：】+ 1 ) 。采用与原问题相同的目标函数，可继续求解每一个线性 规划子问题。 如果没有子问题具有整数最优解，需要将一个子问题再继续分枝为两个子问 题，优先选择目标值最小( 目标函数求极小) 的子问题进行“分枝”；如果某一 子问题具有整数最优解，那么这个整数解及其所对应的目标值将作为可能的最优 解和最优值被记录下来。具有整数最优解的子问题是不需要进一步“分枝”的， 因为进一步的分枝是通过增加约束条件来实现的，而增加约束不会使最优目标函 数值变得更小。 如果在“分枝”求解过程中，出现一个新的子问题有更小的整数解值，则用 新的整数解值代替原有记录的整数解值。当所有的非整数解值都大于被记录下来 的整数解值时，当前记录下来的整数最优值就是整数规划的最优值，对应的最优 解就是整数规划的最优解。分枝的过程只要合适就继续下去，直到每一子问题均 得到一个整数解或者明显看出不能产生一个更好的整数解为止。引进“定界”这 一概念可以提高计算效率，这个概念表明，如果一个子问题的非整数最优解产生 一个比已得到的最好整数解还差的目标值，那么这个子问题就不值得进一步研究 下去了。换句话讲，一旦求出一个可行整数解，那么它的相应目标值就可以用来 作为一个上界，以便舍去那些目标值已经超过该上界的子问题。 9 硕士学位论文 3 背包问题的一种新算法：降维递归算法 3 1 问题的基本特性 经过多年的研究，人们发现，背包问题解决的难易程度，在很大程度上决定 于数据实例1 。也就是说，在某些情况下，背包问题很容易得到解决，而在有些 情况下，却会非常困难。本节将根据物品的性价比的差别，将背包问题的数据实 例分为以下四个类型阳1 并对其进行简单的分析和说明。 1 ) q 与c ：无关的情况 在这种情况下，选择物品f 的效益与选择物品f 花费的代价无关，例如，集 装箱的装箱问题，小型对象有可能非常有价值，然而那些大块头的东西却未必。 这种情况的背包问题利用比较容易解决，因为物品的a f 差异很大，背包很容易 装满，而且很容易通过上界测试的剪枝策略去掉很多没必要扩展的节点。 2 ) q 与q 弱相关的情况 这种情况下，e 只是在a f 的周围有小幅的震动，这种情况正是投资管理中 经常碰到的情况，因为投资领域正是产出正比于投入并且有小幅震动的情况。在 这种情况下，用定上界的方法很难消除变量，但是由于a f 差异很大，背包很容 易装满，而此种情况下得出的可行解与最优解之间的效益比较接近。 3 ) a f 与c ：f 强相关的情况 这种情况基本上就是现实生活中的产出正比于投入的情况。这种情况在背包 问题的研究中是很棘手的，原因有- - ：其一是由于对象的重量都很近似，因此很 难做出选择，把背包填满；其二是不可能通过通过上界的测试将节点剪枝。 4 ) 最大子集和实例 这种情况下，e 与q 完全一样，背包问题就成为把背包装满的问题，这种 情况下，上界法剪枝已经完全失效，因为任何节点的上界均相同。此种问题很难 解决。当然，背包问题的求解难易程度还取决问题的规模n ，物品的重量a 的 域值范围以及背包的大小b 。 1 0 背包问题的一种新算法：降维递归算法 一一 3 2 背包问题的若干性质 性质i ：对于问题( p ) ，若吼哆且q 巳则( 尸) 必有瓤= 0 的最优解。 证：设为( z1 ，zi ，zj ，zn ) f o - j 题( p ) 的最优解，则 ( z 1 z i 一1 ，0 ，z 件1 ，z f 一1 ，z j + z i ，z j + 1 ，z 馆) 一定是问题( 尸) 的可行解 口1 zl + + n t i xi 一1 + a 。0 + a 件l 。件1 + + 口j - i xj l + aj ( zj + z i ) + a j + i xj + l + + 口“z 。 5 善。n tzt + ( 口j 一口i ) zi = 6 + ( 口j a ) x f b 凼此 c l z l 十+ c i 一1 z i 一1 + c , o + c i + l x i + l + + c j l z 卜1 + c j ( x j + z ) + c j + i x j + 1 + + c n z n 2 丢。c tx 。+ ( c 一，) 工， 歪。c 。石。 故必有( z 1 z ，0 ，z 件1 ，2 j l ，z j + z i ，z 件l ，z 佗) 也是( p ) 的最优解 若c ， c 则( p ) 的所有最优解的第i 个分量毛20 ，若c ，c ，则( p ) 至少有 一个最优解的第i 个分量甄：0 、 口 推论1 ：对于问题( p ) ，若q 善后j n j 且c f 善吃勺则p ) 必有屯= o 的 最优解( s i2 1 ，2 ，n ) i ) ) ( = 1 ，2 ，n ) ，一为非负整数。 定义1 ：如果( p ) 存在某个分量吃= 0g = 1 ，2 ，死) 的最优解，则称 硕士学位论文 为研究与分析问题把( p ) 松弛成相应的如下线性规划问题( p 0 ) 。 ( p0 ) ： n m a x 兀= c t z i = 1 n s t a izt b l = 1 z l d 且取整数，墨o ( i = 2 ，3 ，佗) 其中q ，q ，6 均为大于零的整数 在本文中我们约定( p o ) 中的变量是按序列 e j = c ja j ，歹= 1 ，2 ，凡) 的非 增顺序排列的。 性质 2 ： 设x = ：，z 喜，z ：) ，其中x ：= 6 口。 ， j i i ( 6 一k 篁= i 口。x ：r ) 口， ( i = 2 ，n ) ，( 即由贪婪算法得到的解，【x 】表示不大于 z 的最大整数) 。则x = p ：，z ：，z ：) 是( p ) 的一个可行解。 性质 3 ：设x 。：( z ，z 2 ，0 一，。) 其中 工：i = 6 口 ， zo = ( 6 一a 1z ? ) o2 其余分量为零，则x 。= ( x o ，x o ，o ，0 ) 是 ( p o ) 的最优解。 性质4 ：设2 = i ( x ) ，l = y o ( x o ) ，则z m a xf ( x ) l 证：因为( p ) 的可行解集是( p o ) 的解集的子集，又l = y o ( x o ) 是( p o ) 的最优解，故m a xf ( x ) l ，x = ( z ：，z ；，z ：) 是( p ) 的可行解，故 f f ( x 木) m a x f ( x ) l 证毕 定理1 ：若l l 1 则( z ：，x 2 术，z 轰) 是( 尸) 的最优解 证：由件质4 容易得到结论。 1 2 背包问题的一种新算法：降维递归算法 3 3 算法的设计思想和算法步骤 我们回过头来换一种思路来解2 2 中的例子 例m a xf = 4 墨+ 5 五+ 6 墨 s t 3 x l + 4 x 2 + 5 置1 0 五o 且为整数，( i = 1 ，2 ，3 ) 解：根据性质( 2 ) 求得原问题( p ) 的一个可行解为：7 x = ( 3 ，0 ，0 ) 对应的值为：l = 4 x 3 + 5 x o + 6 xo = l2 根据性质( 3 ) 求其对应松弛问题( 尸0 ) 的最优解为 膏= c 半 ，( 1 。一 半 川卟叫， 最优值为：l = 4 3 + 5 0 2 5 + 6x0 = 13 25 根据性质( 4 ) 12 m8x ，( x ) 13 5 ，分别令x1 = 0 ，1 ，2 此时对应松弛问题 的最优解分别为1 2 4 ，1 2 6 ，1 3 。原问题的按贪婪算法到的可行解对应值为：l o ， 9 ，1 3 。max 12 ，10 ，9 ，l3 = l3 故13 max ，( x ) 此时当x 。= 0 ，1 时其对应松弛为题的最优值为1 2 4 ，1 2 6 小于原问题的可行 解对应值为1 3 ，即五的值只能取3 或者2 ，此时原来有3 个变量的背包问题就 转变为只有2 个变量的背包问题并且容量也相应的减小。当五= 3 ：原问题只有 一个可行解，其对应的值为1 2 。当x i = 2 时：对应松弛为题的最优值为1 3 ，由 贪婪算法得到的可行解的对应值也为1 3 。这就说明了在五= 2 这一支对应原问 题的最优值为1 3 。故m a x i ( x ) = 1 2 ，1 3 ) = 1 3 对应的最优解为x = ( 2 ，1 ，0 ) 根据上例的思想，我们设计背包问题的新算法的步骤如下： 预备被初始化工作：根究性质1 及其推论尽可能的除去问题( p ) 中的无效变 量，对( p ) 的剩余变量按序列 e j = c j 口j ，歹= l ，2 ，竹) 的非增顺序进行排列， 把( p ) 相应的松弛成线性规划问题( p o ) 1 3 硕士学位论文 ( 1 ) ：用贪婪算法求出原问题( p ) 的一个可行解x + = 0 ：，z ；，z ：)其中 i - 1 z ：= b 口，】，z ：= ( 6 一k = l 岔t z ：) 。t 】，o = 2 ，3 ，佗) ，求出其对应松弛问题 ( p 0 ) 的最优解设为：xo = ( z ，z2 ，0 ，0 ) ，z 2 = 【b a 1 】， z 2 = p a , x * 1 a z ) 。记2 = f ( x 木) 工：o ( x o ) ，若l l 1 则问题的一 个最优解已求得为x = ( z ：，x2 ，z ：) ，算法终止。 ( 2 ) ：l z 1 ，由x 车是原问题( p ) 的一个可行解故m a xf ，( x ) = z ，构 造善：个新的线性规划问题如下： 懈群= 墨c i z 。+ q 墨( 后= 1 ，2 ，z ：) n s t oizi b a l z l 扛2 z l = z ：一七，z i 0 且取整数o = 2 ，n ) 分别求其相应松弛问题的最优解，设其对应的最优值，：。显然 【， ) ，( 后= 1 ，2 ，z ：) 是单调递减的。若存在一个使得，i z 厂，1 ，这 表示原问题的最优解中的第一个分量z 1 z ：，z ：一1 ，z ：一j + 1 ) 。在多 数情形下j 的值只能取一个比较小的正整数。 ( 3 ) ：这样解一个刀个变量的背包问题就转化为解j 个对应的( n 1 ) 个变量的背包 问题( 随着维数的递减容量也递减的背包问题) 。设其按贪婪算法得到的可行解 对应的值为f ：( i = 1 ，2 ，力和对应松弛问题的最优值为o ( i = 1 ，2 ，歹) ， 若存，：一，? 1 则这一枝的最优解已经求得，这一枝不再往下递归。令 l = m a x ，m a x f * ，( i = 1 ，2 ，歹) ) ) ，若存在，? z 则全局最优值必定不会出现 在这一枝，剪去这一枝。令三= m a ) 【扩? ，ies s 为可行支的指标集，显然l 随着 维数的递减其值递增而三则是递减的。若三一z 1 则全局最优解已求得，z 就 1 4 背包问题的一种新算法：降维递1 月算法 是其最优值，算法终止。 ( 4 ) ：若l z 1 则继续递归把( 竹一1 ) 个变量的背包问题转换为( n 一2 ) 个变量的 背包问题。由于而检验条件l 是递增的是递减的，且m 一2 ) 个变量的背包问题 对应松弛问题的最优值随着维数递减，故在多数情形下大多数分枝是不可行的。 若条件工一z 1 一直不能满足，则递归最后得到的j 就是全局最优值。 1 5 硕士学位论文 4 两个实例及算法评价 本章我们引入二个实例，用新算法求解，并将其与动态规划法相比较，可以 发现用新算法求解让计算量大为减少。 例l ：本例来源于文献 6 m a x ，= 2 6 x1 + 12x2 + 1l x3 + 20 x4 + 9x5 + 16 x6 + 7z7 + 6 x8 + 2o x9 + 16 x1 0 s 芒 24z1 + 11z2 + 10z3 + 18z4 + 8z5 + 14z6 + 6z7 + 5z8 + 16z9 + 12z1 0 46 z ( i = 1 ，2 ，1o ) 为非负整数 解： ( 1 ) 除去原问题中的无效变量，对原问题的剩余变量按序列 e j = c j aj ，j = 1 ，2 ，n ) 的非增顺序进行排列得到 ( p ) m a x ，= 1 6 xl o + 2 0 x9 + 6 x8 + 7 x7 + 9 x 5 s t 12z 1 0 + 16z9+5 z8+6 z7 +8 z 5 4 6 z1 0 ，z9 ，z8 ，z7 ，z5 为非负整数 其对应的松弛问题为 ( p o ) m a x ，= 1 6 x l o + 2 0 x 9 + 6 x s + 7 x 7 + 9 x 5 s t 1 2 x l o + 1 6 x 9 + 5 x s + 6 x 7 + 8 x 5 4 6 z 1 0 为非负整数，其余变量非负 求得( p ) 的可行解为( 3 ，0 ，2 ，0 ，0 ) ，z = f ( x 木) = 6 0 ( p o ) 的最优解为( 3 ，0 625 ，0 ，0 ，0 ) ，三= 0 ( x o ) = 6 0 5 由于l z = 0 5 1 ，故( 3 ，o ，2 ，0 ，0 ) 就是( p ) 的最优解， 原问题的最优解为( o ，o ，0 ，0 ，o ，o ，o ，2 ，0 ，3 ) 口 1 6 背包问题的一种新算法：降维递归算法 例2 ：一个含有3 0 个变量的背包问题，背包容量b = 3 2 0 3 表4 1 a i 数据表 表4 - 2 c ；) 数据表 我们以c i 为纵轴，以a i 为横轴描出( a i ，c f ) 散点图，从下图4 _ l 可以看出a f 与c 是强相关的，属于不容易求解的背包问题。 ， 2 0 5 2 1 0 、2 152 2 02 2 5 解：根据性质2 和性质3 得： 图4 - 1 1 7 3 2 2 1 1 2 2 2 2 2 硕士学位论文 表4 3 对应松弛问题的最优 原问题可行解的对 x 1 值l应值z厶 m a x h ) 1 63 2 1 9 0 13 2 1 6 1 53 2 1 9 0 13 2 1 7 1 4 3 2 1 93 2 1 8 1 33 2 1 93 2 1 9 1 23 2 1 93 0 1 8 1 13 2 1 8 9 93 0 1 9 0 1 03 2 1 8 9 93 0 2 0- 9 3 2 1 8 9 83 0 2 1_ 83 2 1 8 9 83 0 2 2- 73 2 1 8 9 73 0 2 3 63 2 1 8 9 73 0 2 4 0 53 2 1 8 9 63 0 2 5 43 2 1 8 9 6 3 0 2 6 33 2 1 8 9 53 0 2 70 23 2 1 8 9 53 0 2 8 13 2 1 8 9 43 0 2 9_ 03 2 1 8 9 43 0 3 0 0 根据性质4 ：必有3 2 19 = ，m a xf ( x ) l = 3 2 1 9 0 1 根据定理1 ：即有m a xf ( x ) = 3 21 9 ，原问题的最优值已经求出，但还没有得到对应 的最优解 由表4 3 可知，必定存在一个最优解其第一变量x 。= 13 表4 4 对应松弛问题的 原问题可行解的 五屯 工f m a x l i 最优值三 对应值， 1 333 2 1 93 2 1 9 x 1 323 2 1 93 0 1 7 1 3l 3 2 1 8 9 93 0 1 8_ 1 303 2 1 8 9 93 0 1 9 0 当- - - 1 3 ，x 2 = 2 时，原问题也有唯一的可行解x = ( 13 ，2 ，0 ，0 ) ，其对应值 1 8 背包问题的一种新算法：降维递归算法 为3 0 1 7 。此解不是最优解。 当而= 1 3 ，x 2 - - - 3 时，原问题只有唯一的可行解x = ( 1 3 ，3 ，0 ，0 ) ，其对应值 为3 2 1 9 。即x = ( 1 3 ，3 ，0 ，0 ) 就是原问题的最优解。 口 此算法是背包问题的精确算法，与动态规划算法相比较计算量大为减少，但 是此算法并不是多项式算法，对于个别实例其计算的复杂度仍不能让人满意。 1 9 硕士学位论文 参考文献 1 钱迪颂运筹学 m 北京：清华大学出版社，1 9 9 0 2 管梅谷郑汉鼎线性规划 m 山东：山东科学技术出版社，1 9 8 3 3 梁开福背包问题的性质研究 j 数学理论与应用2 0 0 0 ，( 2 ) ：2 3 - - 2 7 4 高天王梦光特殊一维背包问题的降维替换算法研究 j 系统工程理论 方法应用2 0 0 2 ，( 2 ) ：1 2 5 - 1 3 0 5 马仲蕃，魏权龄，赖炎连数学规划讲义，中国人民大学出版社 m ，1 9 8 1 ， 13 3 - 1 4 7 6 吴航运筹学中的转化思想 j 运筹与管理2 0 0 3 ，( i ) ：6 8 7 崔耀东杨绍增背包问题的两阶段动态规划算法 j 高校应用数学学报， 1 9 9 3 ，( 4 ) ：4 3 0 6 4 3 5 8 卢开澄组合数学算法与分析 m 北京：清华大学出版社，1 9 8 3 1 4 7 - 1 6 9 9 郑杨凡基于属性论的0 - 1 背包问题算法研究 d ： 硕士学位论文 上海： 上海海事大学计算机与