貪心法求解一般背包問題的教學探討

余亮　柯昌博　趙學健

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

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

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

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

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

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

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

2 選取單位重量價值作為最優(yōu)量度標準的數(shù)學依據(jù)

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

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

其中：第1個為最小化條件；第2和第3個為原問題可行性條件；第4個為對偶問題可行性條件；第5-7個為互補松弛條件；ηi，εi，λ分別為約束xi?0，xi?1以及∑wixi-M的對偶變量。由于建模的問題是凸問題，滿足上述條件的解同時也為最優(yōu)解。下面分三種情況進行討論：①當-pi+λwi>0時，有ηi>0，由條件5可知，必有xi=0。②當-pi+λwi<0時，有εi>0，由條件6可知，必有xi=1。③當-pi+λwi=0時，有ηi=εi=0，此時xi=0或xi=1或等于（M-∑wi'xi'）/wi，i'≠i）。換句話說，要得到最優(yōu)的xi，需給出λ的最優(yōu)值λ*，其值由約束∑wixi=M來確定。令λmin=minipi/wi，λmax=maxipi/wi。很明顯，當λ從λmax逐漸減小時，∑wixi會單調(diào)遞增至M，則此時的λ即為λ*。事實上，λ從λmax逐漸減小的過程，等價于貪心法每步?jīng)Q策時選取具有最大單位重量價值的物品的過程。因此，貪心法選取單位重量價值作為最優(yōu)量度標準的數(shù)學依據(jù)在此體現(xiàn)。為了更加直觀地展示該數(shù)學依據(jù)，我們進行了數(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次迭代時，λ等于λmax=2和λmin=0.3333的中間值1.1667，此時，由于物品1和4的單位重量價值均大于1.1667，物品1和4均裝入，故第1次迭代裝入物品的總重量為8。當?shù)Y(jié)束時，最優(yōu)決策是[1，0.5，1，1]，最大價值是17。上述整個物品裝填過程及最終結(jié)果與貪心法中每次選取單位重量價值最大的物品裝包所對應(yīng)的裝填過程和結(jié)果均一致。

3 結(jié)束語

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

參考文獻（References）：

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

出版社，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