求解集值折扣{0-1}背包问题的改进动态规划算法

王茂萍 潘大志,2*

1(西华师范大学数学与信息学院 四川 南充 637009) 2(西华师范大学计算方法与应用研究所 四川 南充 637009)

0 引 言

折扣{0-1}背包问题(Discounted{0-1} Knapsack Problem, D{0-1}KP)[1-4]是典型的组合优化问题，D{0-1}KP的模型及求解算法在资源配置、资金预算和项目决策等诸多领域具有重要的理论意义和使用价值[5-7]，随着应用背景逐渐广泛，针对不同的实际问题，寻求新的模型及其求解算法变得越来越重要。针对生产不同类商品需选择不同生产机械和模具的实际问题，提出D{0-1}KP的扩展模型，即集值折扣{0-1}背包问题(D{0-1}KPS)。

1 D{0-1}KPS的定义及数学模型

定义1(D{0-1}KPS) 给定N个均含3个项(或物品)的类别，设第i(1≤i≤N)个类别中第j(1≤j≤3)个项对应的价值和重量分别为pij和wij。其中每个类别的第3项是该类别中前两项的折扣项，其价值系数pi3和重量系数wi3分别满足：pi3=pi1+pi2，wi3∈[max{wi1,wi2}+1,wi1+wi2-1]，每个类别的项可以同时选择，但当某个类别中的项被选中时，会产生固定成本和固定背包容量消耗，其大小由负整数ti和非负整数ai表示。给定一个容量为C的背包，如何选择项装入背包，在容量限制下使得净利润最大？

D{0-1}KPS的数学模型描述如下：

(1)

(2)

xij≤yi∀i∈{1,2,…,N} ∀j∈{1,2,3}

(3)

xij,yi∈{0,1} ∀i∈{1,2,…,N} ∀j∈{1,2,3}

(4)

式(3)表示只有当类别被选中时，该类别中的项才拥有被选中的机会；决策变量xij表示第i个类别中第j个项是否被装入背包；yi表示第i个类别是否被选中。

2 求解D{0-1}KPS的改进DP算法

DP算法[8-12]是20世纪50年代初美国数学家Bellman等在研究多阶段决策过程的优化问题时所提出的，是一种强大的算法设计技术，其核心思想是分而治之，将问题划分为子问题，通过递推公式保存子问题的最优解，避免重复计算，用于求解背包问题具有良好的效果。

2.1 D{0-1}KPS的子模型

D{0-1}KPS与D{0-1}KP不同，当某个项被选择时，需考虑以下四个因素：价值、重量、固定成本和固定背包容量消耗。因此在得到D{0-1}KPS的子模型之前，需要进行相关预处理，确定该项所在的类别及在该类别中的顺序号。设某个项对应的编号为k，则k的范围为：1≤k≤3N。

现给出在前k个项中选择项装入背包容量为γ的D{0-1}KPS子问题模型。

定义3(D{0-1}KPS(k,γ)) 当背包容量为γ∈{0,1,…,C}时，前k个项中选择项装入背包，在不超过背包容量γ的情况下，获得利润最大，将该子问题记为D{0-1}KPS(k,γ)。为更好地构造子问题的数学模型，将前k个项中选择装入背包的项集分成两个集合A(k,γ)(1)和A(k,γ)(2)：A(k,γ)(1)由前h(k)-1个类别中所选择的项构成，A(k,γ)(2)由第h(k)个类别中选择的项构成。其模型如下：

(5)

(6)

xij≤yi∀i∈{1,2,…,h(k)},∀j∈{1,2,3}

(7)

xij,yi∈{0,1} ∀i∈{(1,2,…,h(k)},∀j∈{(1,2,3}

(8)

式(5)表示当背包容量为γ时，前k个项中选择项集装入背包时的最大利润，由三部分组成：A(k,γ)(1)中的项集价值总和、A(k,γ)(2)中的项集价值总和、装入背包项集所在类别的固定成本总和；式(6)表示选择项集应满足的重量约束；式(7)表示只有对应类别被选中时，该类别中的物品才拥有被选中的机会；式(8)表示物品和类别的选中情况。

2.2 DP求解D{0-1}KPS

当选择第k项时，需要分以下两种情况进行讨论：

1) 在前k个项中第h(k)类别有其他项被装入背包，代表第h(k)类别被选中，记为D{0-1}KPS(k,γ)(1)，V(k,γ)(1)表示D{0-1}KPS(k,γ)(1)的最优值。

2) 在前k个项中第h(k)类别无其他项被装入背包，代表第h(k)类别未选中，记为D{0-1}KPS(k,γ)(0)，V(k,γ)(0)表示D{0-1}KPS(k,γ)(0)的最优值。

显然D{0-1}KPS(k,γ)的最优值为：max{V(k,γ)(0),V(k,γ)(1)}，以下为DP求解D{0-1}KPS的递推公式：

1) 当k=1时，初始值设定如下：

V(1,γ)(0)=0 0≤γ≤C

2) 当k>1时，需先判断第k个项所属类别是否与第k-1个项所属类别一致，需要分两种情况讨论。

(1)h(k)=h(k-1)

V(k,γ)(0)=V(k-1,γ)(0)0≤γ≤C

(2)h(k)≠h(k-1)

V(k,γ)(0)=max{V(k-1,γ)(0),V(k-1,γ)(1)} 0≤γ≤C

2.3 改进DP算法求解D{0-1}KPS

为了讨论改进动态规划算法求解集值折扣{0-1}背包问题，现给出如下定义：

定义4第k(1≤k≤n)阶段当前所装物品的总重量m、当前所装物品的总价值p和当前所装最后一个物品的类别号h构成一个状态，记作(m,p,h)k。将第k(1≤k≤n)阶段的所有状态所构成的集合称为状态集，记作Rk。

定义5任意给定两个状态(m1,p1,h1)、(m2,p2,h2)，当且仅当m1≤m2且p1≥p2，(m1,p1,h1)≻(m2,p2,h2)，也称(m1,p1,h1)支配(m2,p2,h2)。

定义6(非支配状态) 一个状态(m,p,h)被称为非支配状态，当且仅当满足如下条件：

∃(m,p,h)′∈R:(m,p,h)′≻(m,p,h)

定义7(非支配状态集) 非支配状态集是所有非支配状态的集合，记作D，定义为D={(m,p,h)|∃(m,p,h)′∈R:(m,p,h)′≻(m,p,h)}，将第k(1≤k≤n)阶段的非支配状态集记作Dk。

以下是改进的DP算法求解D{0-1}KPS的递推公式：

1)k=1时，初始状态集设定如下：

R(1)={(0,0,0)(1)，(wh(1),1+ah(1),ph(1),1+th(1),h(1))(1)}

2)k>1时，第k阶段的状态由第k-1阶段的状态组成和产生，首先将Rk-1的状态作为Rk的初始状态，然后分以下两种情况讨论新状态的产生：

(1) 当(m,p,h)k的类别号与h(k)相同，且满足m+wh(k),b(k)≤C时:

R(k)=R(k-1)∪{(m+wh(k),b(k),p+ph(k),b(k),h(k))(k)}

(2) 当(m,p,h)(k)的类别号与h(k)不同，且满足m+wh(k),b(k)+ah(k)≤C时:

R(k)=R(k-1)∪{(m+wh(k),b(k)+ah(k),p+ph(k),b(k)+th(k),h(k))k}

在形成R(k)后，需要利用状态与状态之间的非支配关系进行剪枝，简化第k阶段的状态数量，得到D(k)，即D(k)=ND(R(k))，其中ND是求非支配状态集的运算符。D{0-1}KPS的最优值是Dn中状态的最大价值，即Opt_D{0-1}KPS=max(Dn(:,2))。以下是算法的具体描述：

算法1改进的DP算法

1.R(1)←{(0,0,0)(1)，(wh(1),1+ah(1),ph(1),1+th(1),h(1))(1)};

2.fork←2 ton

3.R(k)←R(k-1);

4.fori←1 tolength(R(k))

5.ifR(k)(i,3)==h(k)

6.ifR(k)(i,1)+wh(k),b(k)>C

7.continue；

8.end if

9.R(k)←{R(k-1),(R(k)(i,1)+wh(k),b(k),R(k)(i,2)+ph(k),b(k),h(k))(k)};

10.else

11.ifR(k)(i,1)+wh(k),b(k)+ah(k)>C

12.continue；

13.end if

14.R(k)←{R(k-1),(R(k)(i,1)+wh(k),b(k)+ah(k),R(k)(i,2)+ph(k),b(k)+th(k),h(k))(k)};

15.end if

16.end for

17.D(k)←ND(R(k));

18.end for

19.Opt_D{0-1}KPS=max(Dn(:,2))

算法1中，第1行表示第一阶段的状态集；第2-第18行表示第2-第n阶段状态集的情况处理，其中第5-第9行表示当(m,p,h)(k)的类别号与h(k)相同时，产生新状态的情况处理；第11-第16行表示当(m,p,h)(k)的类别号与h(k)不同时，产生新状态的情况处理；第17行表示运用状态之间的支配与非支配关系对Rk进行剪枝，得到非支配解集D(k)；第19行表示得到D{0-1}KPS的最优值Opt_D{0-1}KPS。

3 D{0-1}KPS实例计算

实例1给定两个类别(N=2)，每个类别中包含3个项，其中前两项的折扣项为每个类别中的第三个项，每个类别对应的固定成本为t={-4,-2}，背包容量消耗为a={1,2}，价值集P1={6，8，14，5，7,12}，重量集W1={7,8,10,5,7,9}，背包容量C=32，求此D{0-1}KPS的最优值及其最优解。

由D{0-1}KPS得定义可知，实例1对应的数学模型为：

maxz=6x1,1+8x1,2+14x1,3+5x2,1+7x2,2+

12x2,3+(-4y1)+(-2y2)

s.t. 7x1,1+8x1,2+10x1,3+5x2,1+7x2,2+9x2,3+

y1+2y2≤32

xij≤yi∀i∈{1,2} ∀j∈{1,2,3}

xij,yi∈{0,1} ∀i∈{1,2} ∀j∈{1,2,3}

运用算法1得到如图1所示的状态转换图。

图1 实例1的状态转换图

由图1可知，D(6)={(0,0,0)(6),(7,3,2)(6),(9,5,2)(6),(11,10,1)(6),(16,15,2)(6)，(18,17,2)(6),(19,18,1)(6),(22,20,2)(6),(26,21，2)(6),(28,23,2)(6),(30,28,2)(6)}，因此实例1的最优值为28，最优解为X=[0,1,1,0,0,1]。

4 结 语

本文提出一种有效求解集值折扣{0-1}背包问题的改进动态规划算法。基于DP算法求解D{0-1}KPS的递推公式，结合状态之间的支配与非支配关系，得到每个阶段的非支配状态集，D{0-1}KPS的最优值是第n阶段的非支配状态集中状态的最大价值。运用改进DP算法求解D{0-1}KPS，在形成状态转换图的过程中，减少了记录的状态数，为今后探究折扣背包模型提供了一种参考，接下来不妨从求解速率方向考虑，探究一种优化算法，当面对大规模值折扣{0-1}背包问题时，可以快速达到精确解。