求解集值折扣{0-1}背包問(wèn)題的改進(jìn)動(dòng)態(tài)規(guī)劃算法

王茂萍 潘大志,2*

1(西華師范大學(xué)數(shù)學(xué)與信息學(xué)院 四川 南充 637009) 2(西華師范大學(xué)計(jì)算方法與應(yīng)用研究所 四川 南充 637009)

0 引 言

折扣{0-1}背包問(wèn)題(Discounted{0-1} Knapsack Problem, D{0-1}KP)[1-4]是典型的組合優(yōu)化問(wèn)題，D{0-1}KP的模型及求解算法在資源配置、資金預(yù)算和項(xiàng)目決策等諸多領(lǐng)域具有重要的理論意義和使用價(jià)值[5-7]，隨著應(yīng)用背景逐漸廣泛，針對(duì)不同的實(shí)際問(wèn)題，尋求新的模型及其求解算法變得越來(lái)越重要。針對(duì)生產(chǎn)不同類(lèi)商品需選擇不同生產(chǎn)機(jī)械和模具的實(shí)際問(wèn)題，提出D{0-1}KP的擴(kuò)展模型，即集值折扣{0-1}背包問(wèn)題(D{0-1}KPS)。

1 D{0-1}KPS的定義及數(shù)學(xué)模型

定義1(D{0-1}KPS) 給定N個(gè)均含3個(gè)項(xiàng)(或物品)的類(lèi)別，設(shè)第i(1≤i≤N)個(gè)類(lèi)別中第j(1≤j≤3)個(gè)項(xiàng)對(duì)應(yīng)的價(jià)值和重量分別為pij和wij。其中每個(gè)類(lèi)別的第3項(xiàng)是該類(lèi)別中前兩項(xiàng)的折扣項(xiàng)，其價(jià)值系數(shù)pi3和重量系數(shù)wi3分別滿(mǎn)足：pi3=pi1+pi2，wi3∈[max{wi1,wi2}+1,wi1+wi2-1]，每個(gè)類(lèi)別的項(xiàng)可以同時(shí)選擇，但當(dāng)某個(gè)類(lèi)別中的項(xiàng)被選中時(shí)，會(huì)產(chǎn)生固定成本和固定背包容量消耗，其大小由負(fù)整數(shù)ti和非負(fù)整數(shù)ai表示。給定一個(gè)容量為C的背包，如何選擇項(xiàng)裝入背包，在容量限制下使得凈利潤(rùn)最大？

D{0-1}KPS的數(shù)學(xué)模型描述如下：

(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)表示只有當(dāng)類(lèi)別被選中時(shí)，該類(lèi)別中的項(xiàng)才擁有被選中的機(jī)會(huì)；決策變量xij表示第i個(gè)類(lèi)別中第j個(gè)項(xiàng)是否被裝入背包；yi表示第i個(gè)類(lèi)別是否被選中。

2 求解D{0-1}KPS的改進(jìn)DP算法

DP算法[8-12]是20世紀(jì)50年代初美國(guó)數(shù)學(xué)家Bellman等在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)所提出的，是一種強(qiáng)大的算法設(shè)計(jì)技術(shù)，其核心思想是分而治之，將問(wèn)題劃分為子問(wèn)題，通過(guò)遞推公式保存子問(wèn)題的最優(yōu)解，避免重復(fù)計(jì)算，用于求解背包問(wèn)題具有良好的效果。

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

D{0-1}KPS與D{0-1}KP不同，當(dāng)某個(gè)項(xiàng)被選擇時(shí)，需考慮以下四個(gè)因素：價(jià)值、重量、固定成本和固定背包容量消耗。因此在得到D{0-1}KPS的子模型之前，需要進(jìn)行相關(guān)預(yù)處理，確定該項(xiàng)所在的類(lèi)別及在該類(lèi)別中的順序號(hào)。設(shè)某個(gè)項(xiàng)對(duì)應(yīng)的編號(hào)為k，則k的范圍為：1≤k≤3N。

現(xiàn)給出在前k個(gè)項(xiàng)中選擇項(xiàng)裝入背包容量為γ的D{0-1}KPS子問(wèn)題模型。

定義3(D{0-1}KPS(k,γ)) 當(dāng)背包容量為γ∈{0,1,…,C}時(shí)，前k個(gè)項(xiàng)中選擇項(xiàng)裝入背包，在不超過(guò)背包容量γ的情況下，獲得利潤(rùn)最大，將該子問(wèn)題記為D{0-1}KPS(k,γ)。為更好地構(gòu)造子問(wèn)題的數(shù)學(xué)模型，將前k個(gè)項(xiàng)中選擇裝入背包的項(xiàng)集分成兩個(gè)集合A(k,γ)(1)和A(k,γ)(2)：A(k,γ)(1)由前h(k)-1個(gè)類(lèi)別中所選擇的項(xiàng)構(gòu)成，A(k,γ)(2)由第h(k)個(gè)類(lèi)別中選擇的項(xiàng)構(gòu)成。其模型如下：

(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)表示當(dāng)背包容量為γ時(shí)，前k個(gè)項(xiàng)中選擇項(xiàng)集裝入背包時(shí)的最大利潤(rùn)，由三部分組成：A(k,γ)(1)中的項(xiàng)集價(jià)值總和、A(k,γ)(2)中的項(xiàng)集價(jià)值總和、裝入背包項(xiàng)集所在類(lèi)別的固定成本總和；式(6)表示選擇項(xiàng)集應(yīng)滿(mǎn)足的重量約束；式(7)表示只有對(duì)應(yīng)類(lèi)別被選中時(shí)，該類(lèi)別中的物品才擁有被選中的機(jī)會(huì)；式(8)表示物品和類(lèi)別的選中情況。

2.2 DP求解D{0-1}KPS

當(dāng)選擇第k項(xiàng)時(shí)，需要分以下兩種情況進(jìn)行討論：

1) 在前k個(gè)項(xiàng)中第h(k)類(lèi)別有其他項(xiàng)被裝入背包，代表第h(k)類(lèi)別被選中，記為D{0-1}KPS(k,γ)(1)，V(k,γ)(1)表示D{0-1}KPS(k,γ)(1)的最優(yōu)值。

2) 在前k個(gè)項(xiàng)中第h(k)類(lèi)別無(wú)其他項(xiàng)被裝入背包，代表第h(k)類(lèi)別未選中，記為D{0-1}KPS(k,γ)(0)，V(k,γ)(0)表示D{0-1}KPS(k,γ)(0)的最優(yōu)值。

顯然D{0-1}KPS(k,γ)的最優(yōu)值為：max{V(k,γ)(0),V(k,γ)(1)}，以下為DP求解D{0-1}KPS的遞推公式：

1) 當(dāng)k=1時(shí)，初始值設(shè)定如下：

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

2) 當(dāng)k>1時(shí)，需先判斷第k個(gè)項(xiàng)所屬類(lèi)別是否與第k-1個(gè)項(xiàng)所屬類(lèi)別一致，需要分兩種情況討論。

(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 改進(jìn)DP算法求解D{0-1}KPS

為了討論改進(jìn)動(dòng)態(tài)規(guī)劃算法求解集值折扣{0-1}背包問(wèn)題，現(xiàn)給出如下定義：

定義4第k(1≤k≤n)階段當(dāng)前所裝物品的總重量m、當(dāng)前所裝物品的總價(jià)值p和當(dāng)前所裝最后一個(gè)物品的類(lèi)別號(hào)h構(gòu)成一個(gè)狀態(tài)，記作(m,p,h)k。將第k(1≤k≤n)階段的所有狀態(tài)所構(gòu)成的集合稱(chēng)為狀態(tài)集，記作Rk。

定義5任意給定兩個(gè)狀態(tài)(m1,p1,h1)、(m2,p2,h2)，當(dāng)且僅當(dāng)m1≤m2且p1≥p2，(m1,p1,h1)?(m2,p2,h2)，也稱(chēng)(m1,p1,h1)支配(m2,p2,h2)。

定義6(非支配狀態(tài)) 一個(gè)狀態(tài)(m,p,h)被稱(chēng)為非支配狀態(tài)，當(dāng)且僅當(dāng)滿(mǎn)足如下條件：

?(m,p,h)′∈R:(m,p,h)′?(m,p,h)

定義7(非支配狀態(tài)集) 非支配狀態(tài)集是所有非支配狀態(tài)的集合，記作D，定義為D={(m,p,h)|?(m,p,h)′∈R:(m,p,h)′?(m,p,h)}，將第k(1≤k≤n)階段的非支配狀態(tài)集記作Dk。

以下是改進(jìn)的DP算法求解D{0-1}KPS的遞推公式：

1)k=1時(shí)，初始狀態(tài)集設(shè)定如下：

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

2)k>1時(shí)，第k階段的狀態(tài)由第k-1階段的狀態(tài)組成和產(chǎn)生，首先將Rk-1的狀態(tài)作為Rk的初始狀態(tài)，然后分以下兩種情況討論新?tīng)顟B(tài)的產(chǎn)生：

(1) 當(dāng)(m,p,h)k的類(lèi)別號(hào)與h(k)相同，且滿(mǎn)足m+wh(k),b(k)≤C時(shí):

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

(2) 當(dāng)(m,p,h)(k)的類(lèi)別號(hào)與h(k)不同，且滿(mǎn)足m+wh(k),b(k)+ah(k)≤C時(shí):

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

在形成R(k)后，需要利用狀態(tài)與狀態(tài)之間的非支配關(guān)系進(jìn)行剪枝，簡(jiǎn)化第k階段的狀態(tài)數(shù)量，得到D(k)，即D(k)=ND(R(k))，其中ND是求非支配狀態(tài)集的運(yùn)算符。D{0-1}KPS的最優(yōu)值是Dn中狀態(tài)的最大價(jià)值，即Opt_D{0-1}KPS=max(Dn(:,2))。以下是算法的具體描述：

算法1改進(jìn)的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行表示第一階段的狀態(tài)集；第2-第18行表示第2-第n階段狀態(tài)集的情況處理，其中第5-第9行表示當(dāng)(m,p,h)(k)的類(lèi)別號(hào)與h(k)相同時(shí)，產(chǎn)生新?tīng)顟B(tài)的情況處理；第11-第16行表示當(dāng)(m,p,h)(k)的類(lèi)別號(hào)與h(k)不同時(shí)，產(chǎn)生新?tīng)顟B(tài)的情況處理；第17行表示運(yùn)用狀態(tài)之間的支配與非支配關(guān)系對(duì)Rk進(jìn)行剪枝，得到非支配解集D(k)；第19行表示得到D{0-1}KPS的最優(yōu)值Opt_D{0-1}KPS。

3 D{0-1}KPS實(shí)例計(jì)算

實(shí)例1給定兩個(gè)類(lèi)別(N=2)，每個(gè)類(lèi)別中包含3個(gè)項(xiàng)，其中前兩項(xiàng)的折扣項(xiàng)為每個(gè)類(lèi)別中的第三個(gè)項(xiàng)，每個(gè)類(lèi)別對(duì)應(yīng)的固定成本為t={-4,-2}，背包容量消耗為a={1,2}，價(jià)值集P1={6，8，14，5，7,12}，重量集W1={7,8,10,5,7,9}，背包容量C=32，求此D{0-1}KPS的最優(yōu)值及其最優(yōu)解。

由D{0-1}KPS得定義可知，實(shí)例1對(duì)應(yīng)的數(shù)學(xué)模型為：

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}

運(yùn)用算法1得到如圖1所示的狀態(tài)轉(zhuǎn)換圖。

圖1 實(shí)例1的狀態(tài)轉(zhuǎn)換圖

由圖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)}，因此實(shí)例1的最優(yōu)值為28，最優(yōu)解為X=[0,1,1,0,0,1]。

4 結(jié) 語(yǔ)

本文提出一種有效求解集值折扣{0-1}背包問(wèn)題的改進(jìn)動(dòng)態(tài)規(guī)劃算法。基于DP算法求解D{0-1}KPS的遞推公式，結(jié)合狀態(tài)之間的支配與非支配關(guān)系，得到每個(gè)階段的非支配狀態(tài)集，D{0-1}KPS的最優(yōu)值是第n階段的非支配狀態(tài)集中狀態(tài)的最大價(jià)值。運(yùn)用改進(jìn)DP算法求解D{0-1}KPS，在形成狀態(tài)轉(zhuǎn)換圖的過(guò)程中，減少了記錄的狀態(tài)數(shù)，為今后探究折扣背包模型提供了一種參考，接下來(lái)不妨從求解速率方向考慮，探究一種優(yōu)化算法，當(dāng)面對(duì)大規(guī)模值折扣{0-1}背包問(wèn)題時(shí)，可以快速達(dá)到精確解。