余亮　柯昌博　趙學(xué)健

摘 要： 討論了算法分析與設(shè)計(jì)課程中一般背包問題的貪心法求解策略，提出了單位重量?jī)r(jià)值作為最優(yōu)量度標(biāo)準(zhǔn)的數(shù)學(xué)依據(jù)。該數(shù)學(xué)依據(jù)有助于加深學(xué)生對(duì)如何選取最優(yōu)量度標(biāo)準(zhǔn)的理解并提高學(xué)生對(duì)貪心法的掌握程度。

關(guān)鍵詞： 貪心法； 一般背包問題； 最優(yōu)量度標(biāo)準(zhǔn)； 算法設(shè)計(jì)與分析

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)志碼：B 文章編號(hào)：1006-8228（2016）01-71-02

Discussion on the teaching of solving general knapsack problem with greedy method

Yu Liang1， Ke Changbo2， Zhao Xuejian1

（1. College of Internet of Things， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu 210003， China；

2. College of Computer， Nanjing University of Posts and Telecommunications）

Abstract： Greedy method for solving the general knapsack problem in the course of algorithm analysis and design is discussed in this paper， and the mathematical basis of choosing unit weight value as the optimal metric is put forward. The mathematical basis is helpful to deepen students' understanding of how to select the optimal metric and improve the students' mastery of the greedy method.

Key words： greedy methods； general knapsack problem； optimal metric； algorithm design and analysis

0 引言

算法分析與設(shè)計(jì)作為高等教育中計(jì)算機(jī)及其相關(guān)專業(yè)的核心課程[1-2]，旨在培養(yǎng)學(xué)生使用計(jì)算機(jī)分析問題和解決問題的能力。在該課程中，最基本的算法設(shè)計(jì)方法包括分治法、貪心法、動(dòng)態(tài)規(guī)劃法等。貪心法最重要的兩個(gè)關(guān)鍵詞是：最優(yōu)量度標(biāo)準(zhǔn)和最優(yōu)子結(jié)構(gòu)特性。所謂最優(yōu)量度標(biāo)準(zhǔn)是指，可以根據(jù)該量度標(biāo)準(zhǔn)，對(duì)問題實(shí)現(xiàn)多步局部決策求解，雖然在該量度意義下所做的這些選擇都是局部最優(yōu)的，但最終得到的解是全局最優(yōu)解；最優(yōu)子結(jié)構(gòu)特性表示問題的整體最優(yōu)解包含了其子問題的最優(yōu)解。在利用貪心法求解問題時(shí)，第一步要提出量度標(biāo)準(zhǔn)并證明該標(biāo)準(zhǔn)為最優(yōu)量度標(biāo)準(zhǔn)，并證明問題具有最優(yōu)子結(jié)構(gòu)特性。相比最優(yōu)子結(jié)構(gòu)特性的證明而言，提出量度標(biāo)準(zhǔn)并證明該標(biāo)準(zhǔn)為最優(yōu)量度標(biāo)準(zhǔn)更困難，其主要原因是量度標(biāo)準(zhǔn)的選擇是仁者見仁、智者見智，種類可以有很多。在講授貪心法求解一般背包問題時(shí)，通常給出3種量度標(biāo)準(zhǔn)：①每次取價(jià)值最大的物品裝包；②每次取重量最小的物品裝包；③每次將單位重量?jī)r(jià)值最大的物品裝包。然后，通過實(shí)驗(yàn)來證明第3種量度標(biāo)準(zhǔn)在上述標(biāo)準(zhǔn)中是最優(yōu)的。最后，證明選取的第3種量度標(biāo)準(zhǔn)為最優(yōu)量度標(biāo)準(zhǔn)。這樣的講法雖然是循序漸進(jìn)的，有助于學(xué)生逐步理解貪心法求解問題的主要步驟，但也有一個(gè)問題：當(dāng)學(xué)生自己提出的量度標(biāo)準(zhǔn)中不包含標(biāo)準(zhǔn)3時(shí)，利用實(shí)驗(yàn)結(jié)果對(duì)比和證明來判定問題具有最優(yōu)量度標(biāo)準(zhǔn)將不再湊效，這使學(xué)生對(duì)如何選取最優(yōu)量度標(biāo)準(zhǔn)產(chǎn)生困惑。此時(shí)，若能告之學(xué)生單位重量?jī)r(jià)值作為最優(yōu)量度標(biāo)準(zhǔn)的數(shù)學(xué)依據(jù)，讓其明白最優(yōu)量度標(biāo)準(zhǔn)的選取有章可循，并非隨意想象或憑借經(jīng)驗(yàn)得來，則有助于提高學(xué)生學(xué)習(xí)信心和教學(xué)效果。

基于以上觀察，本文將首先給出一般背包問題的數(shù)學(xué)模型，然后提出單位重量?jī)r(jià)值作為貪心法中最優(yōu)量度標(biāo)準(zhǔn)的數(shù)學(xué)依據(jù)，最后通過計(jì)算機(jī)仿真結(jié)果展示本文提出的數(shù)學(xué)依據(jù)與教材中貪心法采用的單位重量?jī)r(jià)值作為最優(yōu)量度標(biāo)準(zhǔn)的一致性。

1 一般背包問題的數(shù)學(xué)模型

一般背包問題可描述如下：現(xiàn)有一個(gè)載重為M的背包和N個(gè)物品（物品可分割），其中第i（1?i?N）個(gè)物品的價(jià)值為pi，重量為wi，試給出一種裝填方式，使得裝入背包物品的總價(jià)值在不超過背包載重的前提下達(dá)到最大。

令xi表示第i個(gè)物品裝入到背包中的部分，則有：0?xi?1。由于所有裝入的物品不應(yīng)超過背包的載重，故有：。最終，所裝入物品總價(jià)值可表示為。根據(jù)一般背包問題的描述，可建立如下數(shù)學(xué)優(yōu)化模型：

2 選取單位重量?jī)r(jià)值作為最優(yōu)量度標(biāo)準(zhǔn)的數(shù)學(xué)依據(jù)

上一節(jié)建立的數(shù)學(xué)優(yōu)化模型為凸優(yōu)化問題[2]，其對(duì)應(yīng)的拉格朗日函數(shù)如下：

根據(jù)KKT最優(yōu)性條件[2]，所建模問題的最優(yōu)解xi必須滿足如下的條件：

其中：第1個(gè)為最小化條件；第2和第3個(gè)為原問題可行性條件；第4個(gè)為對(duì)偶問題可行性條件；第5-7個(gè)為互補(bǔ)松弛條件；ηi，εi，λ分別為約束xi?0，xi?1以及∑wixi-M的對(duì)偶變量。由于建模的問題是凸問題，滿足上述條件的解同時(shí)也為最優(yōu)解。下面分三種情況進(jìn)行討論：①當(dāng)-pi+λwi>0時(shí)，有ηi>0，由條件5可知，必有xi=0。②當(dāng)-pi+λwi<0時(shí)，有εi>0，由條件6可知，必有xi=1。③當(dāng)-pi+λwi=0時(shí)，有ηi=εi=0，此時(shí)xi=0或xi=1或等于（M-∑wi'xi'）/wi，i'≠i）。換句話說，要得到最優(yōu)的xi，需給出λ的最優(yōu)值λ*，其值由約束∑wixi=M來確定。令λmin=minipi/wi，λmax=maxipi/wi。很明顯，當(dāng)λ從λmax逐漸減小時(shí)，∑wixi會(huì)單調(diào)遞增至M，則此時(shí)的λ即為λ*。事實(shí)上，λ從λmax逐漸減小的過程，等價(jià)于貪心法每步?jīng)Q策時(shí)選取具有最大單位重量?jī)r(jià)值的物品的過程。因此，貪心法選取單位重量?jī)r(jià)值作為最優(yōu)量度標(biāo)準(zhǔn)的數(shù)學(xué)依據(jù)在此體現(xiàn)。為了更加直觀地展示該數(shù)學(xué)依據(jù)，我們進(jìn)行了數(shù)值仿真并利用二分搜索快速找到λ*和最優(yōu)裝填決策。參數(shù)設(shè)置如下：M=14，N=4，[p1，p2，p3，p4]=[8，2，3，5]，[w1，w2，w3，w4]=[4，6，3，4]。最終得到的仿真結(jié)果如圖1所示。

從圖1可知，隨著λ的降低，裝填的物品逐漸增加，直至等于背包載重14。第1次迭代時(shí)，λ等于λmax=2和λmin=0.3333的中間值1.1667，此時(shí)，由于物品1和4的單位重量?jī)r(jià)值均大于1.1667，物品1和4均裝入，故第1次迭代裝入物品的總重量為8。當(dāng)?shù)Y(jié)束時(shí)，最優(yōu)決策是[1，0.5，1，1]，最大價(jià)值是17。上述整個(gè)物品裝填過程及最終結(jié)果與貪心法中每次選取單位重量?jī)r(jià)值最大的物品裝包所對(duì)應(yīng)的裝填過程和結(jié)果均一致。

3 結(jié)束語

貪心法求解問題的核心是選取最優(yōu)量度標(biāo)準(zhǔn)。本文對(duì)貪心法求解一般背包問題時(shí)最優(yōu)量度標(biāo)準(zhǔn)的選擇進(jìn)行了探討，并給出了單位重量?jī)r(jià)值作為最優(yōu)量度標(biāo)準(zhǔn)的數(shù)學(xué)依據(jù)。這有助于學(xué)生明白：雖然量度標(biāo)準(zhǔn)的選取可以有很多種，但最優(yōu)的量度標(biāo)準(zhǔn)往往有其背后的數(shù)學(xué)依據(jù)可遵循，并非完全憑借經(jīng)驗(yàn)或隨意想象得來；同時(shí)有助于學(xué)生加深對(duì)選擇最優(yōu)量度標(biāo)準(zhǔn)的理解并提高學(xué)生掌握貪心法的信心。

參考文獻(xiàn)（References）：

[1] 余祥宣，崔國(guó)華，鄒海明.計(jì)算機(jī)算法基礎(chǔ)[M].華中科技大學(xué)

出版社，2006.

[2] 陳慧南.數(shù)據(jù)結(jié)構(gòu)與算法：C++語言描述[M].高等教育出版

社，2005.

[3] S. Boyd and L. Vandenberghe， Convex optimization[M].

Cambridge：Cambridge University Press，2004：1-244