求解集值折扣{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}背包問題的改進動態規劃算法?；贒P算法求解D{0-1}KPS的遞推公式，結合狀態之間的支配與非支配關系，得到每個階段的非支配狀態集，D{0-1}KPS的最優值是第n階段的非支配狀態集中狀態的最大價值。運用改進DP算法求解D{0-1}KPS，在形成狀態轉換圖的過程中，減少了記錄的狀態數，為今后探究折扣背包模型提供了一種參考，接下來不妨從求解速率方向考慮，探究一種優化算法，當面對大規模值折扣{0-1}背包問題時，可以快速達到精確解。