混合背包问题的算法设计与分析

混合背包问题的算法设计与分析

长江大学学报 (然科学版 ) 20年 3第 6第 1:理工自 09月卷期 J unl f agz nvri ( a S i dt ora o n t U ies y N t c E i Ma. 0 9 Y e t ) r2 0 .V 16No 1 c o. .:S i

Eg n

混合背包问题的算法设计与分析王苫社,张宏礼 (龙江八一大学文理学院数学系,黑农垦黑龙江大庆 13 39 6 1)黄体德 (东财政学院东方学山泰安 21o)山院,东 7oo [要]提出了一种更具有实际用处的混合背包问题,并建立了相应的数学模型,然后进行了算法设计以摘及复杂性分析,最后给出了程序主要代码,并利用计算机求解了实例问题,验证了所提出算法的有效性 .

[关键词]混合背包问题;动态规划算法;贪心算法;O1背包问题;背包问题 -[图分类号] T 3 1中 P 0[献标识码] A文

.

[章编号]17文 6 3—10 (0 9 1 N1 7 2 4 9 2 0 O一 1一O J

O1背包问题和背包问题是算法设计与分析领域经典的 NP难题【,在现实中有许多实际应用背景,一 1] 比如船舶的最优装载问题 _等,所以关于它们解法的研究一直是人们热衷讨论的问题 . 2 01背包问题是: -给定种物品和一背包,品重量分别为 W .…, 价值分别为 7,,,背物,, W, 3… 包的容量为 C,何选择装入背包的物品,如使得装入背包中的物品的总价值最大 .选择物品时,每种物在对品只有 2选择,种即装入和不装入,分别用 0和 1示,能装入某种物品的一部分,不能将某种物品装表不也

入多次 .问题具有标准的最优子结构性质和重叠子问题性质,该]因此可以用动态规划算法解决,法的算复杂性为 . n . Q( 2)

与 O 1背包问题类似的背包问题是:定中物品和一背包 .品重量分别为 W W…,,值分一给物,, W价别为,,,背包的容量为 C, …如何选择装入背包的物品,得装入背包中的物品的总价值最大 .使在选

择物品时,种物品可以全部装入,某也可以只装入其中的一部分 .问题具有贪心算法所要求的 2个基本该要素:心选择性质和最优子结构性质,以单位价值作为衡量贪心的标准,容易找到解决该问题的]贪若很贪心算法,其复杂性为 o( o ) lg .但是,在实际的应用中,经常会遇到在可以选择的物品中,有一部分是可以部分装入的,而其余物品只能装入或者不装入的问题 .为此,笔者提出了一种兼有 01包问题和背包问题的,更具有现实用处的 -背混合背包问题,然后建立了相应的数

学模型,进而进行了算法分析和设计,给出了问题的求解方法 .

1混合背包问题设有 2种物品,其重量分别为 w,, w价值分别为,2…,2背包的容量为 C,中位于奇数 lw2…, 2, 7, 7 3 3 其位置的物品可以部分装入背包,而位于偶数位置的物品只有全部装入或不装入 2种选择,计一种算法,得设使装入背包的总价值最大 .这种兼有 0 1称—背包问题和背包问题的问题为混合背包问题,其数学模型如下:2 n

1 ax TI

∑i 1= 2 n

st .

: W≤ C

其中, i=2 (当= k愚一 1 2…,时,{,}当 i 2+ 1是 1 2…,)时,[,] z: 0表示=,, ) .∈ 0 1;一 k z (,, z∈ O 1 .不装入该物品;一 1示全部装入该物品; 表 0< z< 1示装入部分该物品 . 表

引入向量 X一 ( .z,, )混合背包问题即是在上述约束条件下,求向量 X的一组取值,目 z,… ,寻使标函数最大 .在实际的问题中,可能并不一定是完全符合上述情况,但是总可以将问题转化成上述的情

况,比如:如果奇数类物品和偶数类物品种类不同,则可以补充若干重量为 0,价值也为 0的物品,使得奇数类物品和偶数类物品的数量相同.[收稿日期] 2 0—1 0 8 1—2 5

[作者简介]王苫社 ( 9 1 ) 18一,男,2 0 0 4年大学毕业,助教,硕士生,现主要从事图形处理与模式识别方面的研究工作.

混合背包问题的算法设计与分析

长江大学学报 (然科学版 )自

20 09年 3月

由于混合背包问题兼有 01背包问题与及背包问题的特征,所以可以认为是二者的更一般形式,更 -具有实际意义,其解决的方式可以借鉴二者的算法 .但是,由于在选择物品的时候存在 2种不同情况的

选择,使得在选择装入背包物品的种类和数量时难度增大,算法的时间消耗会成倍增加,且附加空间消耗也会相应增加,所以有必要进行新的算法设计与分析 . 混合背包问题具备 2基本性质:贪心选择性质与最优子结构性质 .个 1贪心选择性质 )如果混合背包问题具有最优解,则一定全部装入了或部分装入了单位价值最大的物品 .如果全部装入了该物品,则可以继续该算法,装入其他物品;如果只是部分装入,则其他物品没有被装入就已经产生了最优解 . 2最优子结构性质如果混合背包问题的最优解已经装入了单位价值最大的物品,则产生的子问 )题为 2不同的情况:①如果单位价值最大的物品全部装入了背包,则产生了除去单位价值最大的物品种之后的子问题,可以利用"切割——粘贴"

方法证明,整体问题的最优一定包含了该子问题的最优解 . ②如果单位价值最大的物品部分装入了背包,则产生了子问题更加简单,此时,只有部分单位价值最大的物品被部分装入了背包,已经产生了最优解,剩余的背包容量为 0,因此,整体的最优解一定包含了子问题的最优解 .

根据上述分析,可以尝试利用贪心算法来解决此问题 .基于贪心算法的贪心选择性质,选择单位价值的高低作为贪心衡量的标准,即首先计算各种物品的单位价值,并且依据贪心选择性质的要求,按照单位价值非降序排列 .嘶计

2算法设计与分析下面结合一个实例说明混合背包问题的算法设计与分析 .基于以上的算法分析,该问题的算法设计如下:O

耋 L2 3 LO 5

设背包的容量为 C一 1 9共有 8种物品,…,其重量和价值如表 1 4, a, a,所示:3

7

O

5 5

表 1物品的重量和价值∞5 5 1

1 )判断奇数类物品和偶数类物品的数量是否一致,若不一致则对于较少的物品以补零的形式补齐 .

2 )分别计算奇数位置和偶数位置物品的单位价

值,并且分别将单位价值按照非降序排列 .于只有 2类物品,可用布尔型数确定其类型 .若为 1,则为奇数类,否则为偶数类 .

∞ 23

3 )考虑单位价值最大的物品,首先判断其所属类型,即该物品为奇数类物品还是偶数类物品 .鉴4 )如果为奇数类物品,则判断当前背包容量与该物品重量的大小关系,果当前背包容量 C小于如3 5 5 5

该物品的重量,当前对应的解向量的分量值为 C w,则/其余一 0则求解完毕 .,否则全部装入该物品,继续回到 3,至确定所有 z的值 . )直 i

基于以上的算法设计,以看到,可在开始阶段需要首先计算每种物品的单位价值,设置一个循环即可 . 因此,以在线性 0(可 )时间内完成;次,对单位价值按照非降序排列,用快速排序可以在其要利O no. ( lg )时间内完成;后,最产生最优解阶段也只需在一次循环内完成,所需时间为 0( )综合上述可 .

知,算法的复杂性为 O n o )因为排序本身的渐进最优算法时间复杂性为 O( lg )因此该算法是该 ( lg" . n o,渐进意义下的最优算法,也要充分考虑到最坏情况下的算法复杂性,当混合背包问题退化为 0 1背包但即—问题时,法的复杂性为 n(2 )算 n" .

根据上面的算法设计与分析,前面的实例完整地编

程,先考虑单位价值最大的物品 a,< C,对首 叫.

所以 .一 1依次执行程序可得最优解为[一,., z z -]一[,.,,,,,,],大总价值为 3 9 o0 80 111 11最 9.[考文献]参[]李北斗 .关于 01包问题的算法研究厂] . 0 8 3 5: 3 2 . 1背 J 2 0, 6( ) 2~ 6[]宁爱兵,马良 . -包问题竞争决策算法 _] .计算机工程与应用, 0 8 4() 4 1. 2 01背 J 2 0,4 3:1~ 6

[]尚荣华 .求解多目标的 01背包问题的克隆选择算法[].西安交通大学学报,2 0,4 ( ) 1 2 1 0 3 J 0 8 2 2: 5~ 6[]钟海林 .背包问题的若干性质及问题的简化[] .江西科学, 0 8 6 ( ) 4 - 4 . 4 J 2 0,2 1: 6 7

[辑]洪云飞编

本文来源：https://www.bwwdw.com/article/mm6i.html