基于集合求解01背包問題的跳躍點法

文/王金燕

1 引言

01背包問題的具體描述為：有n個物品，物品i（i=1,2,...,n）的重量為wi，價值為vi，一個背包容量為c。要求從背包的價值出發，做出最優的裝包決策。與背包問題不同，此處的物品不允許劃分，即選擇裝入一個物品就必須裝入其全部。這種01整數的規劃決策問題在當前生活中得到了廣泛的應用，類似問題已經推廣到密碼學、商業資金管理、數學應用計算等多個領域。雖然01背包問題的思想很好理解，但由于其NP復雜性，采用一般的算法很難解決。而動態規劃算法可以通分析，將原問題逐層劃分為若干小問題，通過層層遞歸得到原問題的解。

2 傳統的動態規劃求解策略

對于最終背包所包含的物品，可以形象化的用一個n元01向量(x1, x2, ...xn)表示，其中xi=0表示最優裝包策略不包含第i個物品，xi=1表示最優裝包策略包含第i個物品。則01背包問題則可以抽象為如下數學表達式：

記m(i,j)為一個子問題的最優值。該子問題為：為一個容量為j的背包做決策，選擇第i,i+1,...n個物品中裝入哪些物品。根據最優子結構性質，子問題的遞歸式可以表示為：

顯然，求解m[][]只需遍歷每個物品，時間復雜度為O(c*n),但是當背包容量很大如c>2n時，計算m[][]需要計算時間。

3 改進的跳躍點法求解01背包問題

3.1 算法的提出

很顯然，隨著背包容量的增加，允許裝入背包中的物品有更多的選擇余地，則背包的總價值或者保持不變（不再裝入新的物品），或者階梯狀上升（選擇新的物品裝入），不可能出現背包價值減小的情況。即m(i,j)是一個關于j的單調不減函數。

舉例來說，當n=5，c=10時，假設w={2,2,6,5,4}，v={6,3,5,4,6}

則m(4,j)，m(5,j)的函數圖像如圖1所示。

由于背包的容量存在增加時，背包總價值m(i, j)才會發生改變。即m(i,j)不是隨著j的連續取值而變化的。此外因為物品不可分割，而單個物品的價值往往是大于1的整數，則m(i, j)也并不是連續增加的值，每裝入一個重量為wi的物品，m(i, j)值會跳躍增加相應vi。則將(wi,vi)稱為函數m(i, j)的跳躍點。在m(i, j)的計算中，無需再對其子問題保存的值進行比較和賦值，只需要逐層計算跳躍點，最終的跳躍點即包含了背包的最大價值。

3.2 算法說明

此處假定變量j取連續值，求解過程中每求得一個跳躍點就將其插入到一個set集合中，最終該集合是m(i,j)的全部跳躍點集合，記為p[i].對于任意容量為j的背包（即任一個子問題），建立迭代遍歷跳躍點集p[i]即可確定m(i, j)的值。前面我們已經說明過m(i, j)的非遞減性，所以任一個子問題中的全部跳躍點都是呈階梯狀上升的。

根據遞歸表達式可知，m(i,j)的跳躍點主要包括以下兩類：

①m(i+1,j)的跳躍點集p[i+1];

②m(i+1,j-wi)+vi的跳躍點集q[i+1];

即p[i]=p[i+1]∪q[i+1].

需要注意的是，在所有的跳躍點集中并不全都是正確的跳躍點。下面進行例證：

設(i1, j1)和(i2, j2)都是p[i]中的跳躍點。假設存在一種可能，使得i1≤i2且j2≤j1，說明當背包容量時增加，所包含物品的總價值減少。與前文所述顯然矛盾，即(i2, j2)不是真正的跳躍點。(i2, j2) 受控于(i1, j1)，被稱為受控跳躍點。實際上，受控跳躍點的出現是由于遞歸表達式產生的。當m(i,j)=max {m(i+1,j),m(i+1, j-wi)+vi}時，兩者中相對較小的點并沒有被采用，但卻也包含在跳躍點集中，就成為了受控跳躍點。

③由于受控跳躍點是不正確的跳躍點，p[i]=p[i]-{受控條約點}

3.3 算法實現

（1）變量及操作的定義：

定義跳躍點為結構體變量struct point{int x;int y;}；定義一系列set集合p[i]，q[i]表示全部跳躍點集set p[n]，q[n]；其中，p[i+1]表示m(i+1,j)的跳躍點集，

q[i+1]為子問題m(i+1,j-wi)+vi的跳躍點集。

圖1：m(4，j)m(5，j) 圖像

（2）初始化并加入所有可能的跳躍點：

（3）用迭代器遍歷每個跳躍點集，刪除受控跳躍點。

（4）重復①-③，直到確定p[1]的跳躍點集，該集合中最后一個跳躍點即為所求的背包最大價值。至此算法結束。

4 算法復雜度分析

上述算法的主要計算量在于步驟②-③中的遍歷過程。對p[i]集合的合并求解需要遍歷每個p[i]保存的跳躍點集,判斷并刪除刪除跳躍點集中的受控跳躍點也需要遍歷p[i]，即需要O(|p[i+1]|)的計算時間。而每個跳躍點相應于一個解變量xn序列的01賦值。故p[i]中的元素數目存在上限2n-i+1。從而算法計算跳躍點集所花費的時間為：

5 結語

本文從傳統的動態規劃求解01背包問題出發，根據遞歸表達式研究跳躍點法對于問題的求解，同時提出用STL模板庫中的set集合存儲求解過程中的跳躍點集，避免了重復跳躍點的出現，降低了算法的時間復雜度和空間復雜度。