科學(xué)計(jì)算與信息處理于 淼:“背包問題”算法設(shè)計(jì)及分析“背包問題”算法設(shè)計(jì)及分析

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

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

中圖分類號(hào):TP274文獻(xiàn)標(biāo)識(shí)碼:B

文章編號(hào):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 引 言

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

1 問題描述

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

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

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)先策略的算法設(shè)計(jì)

按重量a1≥a2≥a3≥a4≥…≥an對(duì)xi進(jìn)行調(diào)整，作為待選隊(duì)列[7，8]。

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

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

對(duì)后面等待選擇的物品jk來說，與之對(duì)應(yīng)的ak無疑滿足:

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

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

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

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

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

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

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

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

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

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

3 動(dòng)態(tài)規(guī)劃法的算法設(shè)計(jì)

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

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

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

(3) 建立狀態(tài)轉(zhuǎn)移方程: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) 遞推求解:逐步計(jì)算出f1(s1)，f2(s2)，…，fn(sn)最后求得，fn(a)即為所求的最大價(jià)值。

4 遞歸的算法設(shè)計(jì)

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

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

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

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

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

② 若選擇的一組物體中包括wn，則knap(s，n)的解就是knap(s-wn，n-1)的解。這樣，一組 wn的值就是問題的最佳解，就能將規(guī)模為 n的問題轉(zhuǎ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

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

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

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

5 算法的復(fù)雜度分析

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

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

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

(1) 當(dāng)1個(gè)物品被選擇時(shí)，有一次插入運(yùn)算、n-1次比較運(yùn)算、n-1次篩選隊(duì)列插入運(yùn)算、(l+n-2)(n-1)/2次篩選隊(duì)列排序的比較運(yùn)算和n-2次的加法與n-1次的組合比較運(yùn)算;

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

{[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

其時(shí)間復(fù)雜度為T(n)=O(n2)。

5.2 動(dòng)態(tài)規(guī)劃法的復(fù)雜度分析

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

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

5.3 遞歸算法的復(fù)雜度分析

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

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

6 結(jié) 語

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

參考文獻(xiàn)

[1]王曉東.算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社，2003.

[2]盧開澄.計(jì)算機(jī)算法導(dǎo)引——設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社，1996.

[3]譚浩強(qiáng).C程序設(shè)計(jì)[M].北京:清華大學(xué)出版社，1992.

[4]王春森.程序設(shè)計(jì):高級(jí)程序員級(jí)[M].北京:清華大學(xué)出版杜，1999.

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

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

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

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

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

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