摘 要:“背包問題”是一個典型問題，其求解也是算法設計及驗證的一個熱點。在此分別采用優(yōu)先策略、動態(tài)規(guī)劃及遞歸三種不同方法對 “背包問題”進行求解、算法設計及驗證。實踐證明了三種算法的正確性。在復雜度分析中，優(yōu)先策略算法的空間及時間復雜度最低，而動態(tài)規(guī)劃法具有明顯的優(yōu)勢。

關鍵詞:背包算法;優(yōu)先策略;動態(tài)規(guī)劃;棧操作

中圖分類號:TP274文獻標識碼:B

文章編號:1004-373X(2010)02-128-03

Design and Analysis of Knapsack Problem

YU Miao

(Anshan Meteorological Bureau of Liaoning Province，Anshan，114004，China)

Abstract:Knapsack problem is typical problem in computer science and its solution is a hot spot in algorithms design and verification.The solutions for the knapsack problems，algorithms design and verification with three different means:preference strategy，dynamic programming and recursion.Correctness of these three algorithms are proved，in the complexity analysis，the complexity of space and time in preference strategy is lowest，while the dynamic programming has obvious superiority.

Keywords:knapsack problem;preference strategy;dynamic programming;stack peration

0 引 言

算法研究是計算機科學的重要組成部分，有觀點認為 “計算機科學是一門研究算法的科學”[1，2]，無論這種觀點是否全面，都足以說明算法研究在計算機科學發(fā)展中所具有的重要作用及地位。算法研究是通過程序來實踐的。程序=算法+數(shù)據結構[3，4]，這一大家都熟知的公式更加表明算法研究不是單純的數(shù)學問題，必須通過 “實踐”掌握算法的實質。這里對 “背包問題”采用優(yōu)先策略、動態(tài)規(guī)劃及遞歸三種不同方法進行求解、算法設計及驗證，并通過各種算法予以實現(xiàn)。本文研究、分析了實現(xiàn) “背包問題”算法的實質。

1 問題描述

一旅行者攜帶背包去登山，已知所能隨身攜帶的背包重量限度為 b，現(xiàn)有n種物品可供選擇裝入背包。第i種物品重量為ai，其重要性價值指標為ci，旅行者應如何選擇攜帶各種物品，以使總價值最大[5，6]。

“背包問題”的數(shù)學模型為:

max z=∑ni=1cixi

約束條件為:

∑ni=1aixi≤b，ai>0，ci>0，

xi=0或1， 1≤i≤n

2 優(yōu)先策略的算法設計

按重量a1≥a2≥a3≥a4≥…≥an對xi進行調整，作為待選隊列[7，8]。

假設前面已經選擇了s個，即jr1，jr2，…，jrs為最優(yōu)選擇的前s件物品，則應滿足:

cr1，cr2，…，crs，且∑si=1 ai

對后面等待選擇的物品jk來說，與之對應的ak無疑滿足:

ak≤ari， i=1，2，…，s

即所選擇的物品重量比其所有待選擇的物品重量大。因此，對待選擇的物品是否被選中將分為:∑si=1ari+ak≤b和∑si=1ari+ak>b 兩種情況。

(1) 對于∑si=1ari+ak≤b的情況，將xk插入已選擇的J隊列中，然后根據ci的大小找到其相應的位置。

(2) 對于∑si=1ari+ak>b的情況，有:

① 若存在ck≥cri，則將xk插入并按ci排序后，將jri從已選擇的隊列中刪除并插入按ci從大到小、重量從小到大地排序到二次篩選隊列中。

② 若存在ckcrs的物品xk插入已選擇的J隊列中并按 ci排序，將從已選擇的隊列中刪除并插入按 ci從大到小、重量從小到大排序到二次篩選隊列中;若不存在滿足的待選物品，則將xk插入到二次篩選隊列中。

③ 當待選隊列為空時，選擇隊列從s到1與從二次篩選隊列中選擇的元素進行優(yōu)化選擇。若存在:

∑n-s-mj=1aj+∑s-1i=1ari≤b， ∑n-s-1j=1cj>cri

將組合的各元素Xi插入已選擇的J隊列中，然后根據 ci的大小找到其相應的位置:jri，jr2，…，jrs。

④ 當③中已完成對首元素組合的篩選后，此時的J隊列為最優(yōu)選擇。

3 動態(tài)規(guī)劃法的算法設計

動態(tài)規(guī)劃的基礎是最優(yōu)化原理，其關鍵問題是建立動態(tài)規(guī)劃的數(shù)學模型(狀態(tài)轉移方程)。主要步驟是:劃分階段，確定階段的狀態(tài);確定決策變量、權函數(shù)以及指標函數(shù);建立狀態(tài)轉移方程;根據動態(tài)規(guī)劃的最優(yōu)化原理建立遞歸方程;自底向上遞推逐步求解。

(1) 劃分階段k:將供選擇的物品按 1，2，…，n排序，每個階段可裝入一種物品;

(2) 確定決策變量:xk裝入第k種物品的件數(shù);背包中允許裝入前k種物品的總重量;

(3) 建立狀態(tài)轉移方程:sk=sk-1+akxk;

決策集合為:

D(sk-1)={xk|0≤xk≤[sk/xk]，xk∈Z}

(4) 建立遞歸方程:

fk(sk)=maxxk=0，1，…，\\{fk-1(sk-1- xkak+ ck)}

f0(0)=0

(5) 遞推求解:逐步計算出f1(s1)，f2(s2)，…，fn(sn)最后求得，fn(a)即為所求的最大價值。

4 遞歸的算法設計

遞歸算法的基本思想是假設用布爾函數(shù) knap(s，n) 表示 n件物品放入可容質量為 s的背包中是否有解，當knap函數(shù)的值為真時，說明問題有解，相反當值為假時，無解。這里可以通過輸入s和n的值，進行以下幾種情況的討論。

(1) 當s=0時，可知問題有解，即函數(shù)knap(s，n)的值為true。

(2) 當s<0時，這是不可能的，所以函數(shù)值為1。

(3) 當s>0且n<1 時，即總物品的件數(shù)不足1，這時函數(shù)值為1;只有當s>0且n≥1 時，才符合實際情況，這時又分為兩種情況。即:

① 若選擇的一組物體中不包括wn，則knap(s，n)的解就是knap(s，n-1)的解;

② 若選擇的一組物體中包括wn，則knap(s，n)的解就是knap(s-wn，n-1)的解。這樣，一組 wn的值就是問題的最佳解，就能將規(guī)模為 n的問題轉化為規(guī)模為 n-1 的問題。綜上所述“背包問題”的遞歸函數(shù)定義為:

knap(s，n)=true， s=0

1， s<0

1， s>0且n<1

knap(s，n-1)或knap(s-wn，n-1)，

s>0且n≥1

上述算法對于所有物品中的某幾件恰好裝滿背包時，能準確求出最佳解。一般情況，對于某一些物品無論怎么裝都不能裝滿背包，必須按背包的最大容量來裝。若物品件數(shù)為4，其質量分別為10，2，5，4，背包的容量為 20，則這四件物品無論怎么放都不能恰好裝滿背包，只能最大限度地裝入背包，即必須裝下10，5，4 這三件物品，這樣就能得到最大重量19。

對于這種裝不滿的背包，它的解決辦法是按所有物品的組合質量最大來裝背包的。如果還裝不滿，則可以考慮剩余空間能否裝下所有物品中最小的那件;如果連最小的都裝不下了，此時則說明得到的解是最佳解，問題解決。這樣必須先找出所有n件物品中質量最小的(它的重量為min)，但是為了解決問題，不能增加太多的運算次數(shù)，并且必須運用上述遞歸函數(shù)。

那么可通過修改s的值，即背包的容量，從背包容量s中減去k(它的值是0到大于min-1之間的一個整數(shù)值)，再調用遞歸函數(shù)。當k=0 時，即能裝滿背包，其他值也能保證背包能最大限度裝滿，這樣所有問題都解決了。

5 算法的復雜度分析

5.1 優(yōu)先策略算法的復雜度分析

實現(xiàn)優(yōu)先策略算法所需的存儲空間包括:每個物品的編號、重量、價值為3n;已選擇隊列的存放為3n;篩選隊列為3n;占用的總空間為 9n，其空間復雜度為S(n)=O(n)。

優(yōu)先策略算法執(zhí)行的時間，按選擇隊列形成分為n個物品被選，1個物品被選及n/2個物品被選三種情況。前兩種是最簡單的情況，最后一種是最復雜的情況。在選擇隊列最好情況下，運算次數(shù)為n-1的比較運算和n次的插入運算。

(1) 當1個物品被選擇時，有一次插入運算、n-1次比較運算、n-1次篩選隊列插入運算、(l+n-2)(n-1)/2次篩選隊列排序的比較運算和n-2次的加法與n-1次的組合比較運算;

(2) 當n/2個物品被選擇時，有n-1次比較運算、n/2次插入運算、n/2次篩選隊列插入運算、(1+n/2-1)(n/2-1)/2次篩選隊列排序的比較運算、n/2次的n/2-1次的加法與n/2-1次的組合比較運算，因此其平均執(zhí)行時間為:

{[1+(n-1)+n]+[1+(n-1)+(n-1)+(l+n-2)(n-1)/2+(n-2)+(n-1)]+[(n-1)+n/2+

n/2+(1+n/2-1)(n/2-1)/2+(n/2)(n/2-1+n/2-1)]}/3=(9n2+58n-20)/8

其時間復雜度為T(n)=O(n2)。

5.2 動態(tài)規(guī)劃法的復雜度分析

實現(xiàn)動態(tài)規(guī)劃法所需的存儲空間包括:每個物品的編號、重量、價值為3n;背包i中裝入的物品數(shù)及總重量限定值為2n2;每件物品的重量及價值為2n;占用總的空間為 2n(n+l)，其空間復雜度為S(n)=O(n2)。

算法的執(zhí)行時間為nab次循環(huán)，每一循環(huán)中一次比較及 6次基本運行。算法完成所需總的時間為6n2。因此其時間復雜度T(n)=O(n3)。

5.3 遞歸算法的復雜度分析

實現(xiàn)遞歸算法所需存儲空間包括:每個物品的編號、重、價值為3n，保存當前最佳方案為3n，棧的使用為n2，占用的總空間為n(n+6)，其空間復雜度S(n)=O(n2)。

遞歸算法的執(zhí)行時間為 n2次調用，每次調用中完成一次比較運算和一次棧操作運算，算法完成所需總的時間為2n2，其時間復雜度為T(n)=O(n2)。

6 結 語

以上三種算法都在Turbo C環(huán)境下得以實踐驗證，實踐證明了這三種算法的正確性。通過 “背包問題”的算法設計及實踐可看出，無論優(yōu)選策略算法，還是動態(tài)規(guī)劃算法，都是在給定約束條件的情況下，求最大值數(shù)學模型的建立過程;但最終的算法實現(xiàn)、數(shù)據結構的建立都是在遞歸或棧操作的基礎上完成的。然而當給定的約束條件不同，篩選的條件不一致時，遞推過程的數(shù)據存儲及棧的堆集不同。在復雜度分析中，優(yōu)先策略算法的空間及時間復雜度最低，但就可讀性與模型的一一對應而言，動態(tài)規(guī)劃算法具有其他方法不可比擬的優(yōu)勢[9，10]。

參考文獻

[1]王曉東.算法設計與分析[M].北京:清華大學出版社，2003.

[2]盧開澄.計算機算法導引——設計與分析[M].北京:清華大學出版社，1996.

[3]譚浩強.C程序設計[M].北京:清華大學出版社，1992.

[4]王春森.程序設計:高級程序員級[M].北京:清華大學出版杜，1999.

[5]于秀霞.求解背包問題的新型算法\\.長春大學學報，2002(2):3-5.

[6]李少芳.連續(xù)背包問題貪婪算法最優(yōu)解的實現(xiàn)[J].福建電腦，2003(11):12-13.

[7]何文明，朱起定.背包問題的循環(huán)及并行解[J].湘潭師范學院學報:社會科學版，2000，21(3):49-50.

[8]李慶華，李肯立，蔣盛益，等.背包問題的最優(yōu)并行算法[J].軟件學報，2003，14(5):891-896.

[9]劉西奎，李艷，許進.背包問題的遺傳算法求解[J].華中科技大學學報:自然科學版，2002，30(6):89-90.

[10]虞安波，楊家本.多背包問題的遺傳算法求解\\.計算機技術與自動化，2002(2):59-63.