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

余亮　柯昌博　趙學健

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

關鍵詞： 貪心法； 一般背包問題； 最優量度標準； 算法設計與分析

中圖分類號：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 引言

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

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

1 一般背包問題的數學模型

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

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

2 選取單位重量價值作為最優量度標準的數學依據

上一節建立的數學優化模型為凸優化問題[2]，其對應的拉格朗日函數如下：

根據KKT最優性條件[2]，所建模問題的最優解xi必須滿足如下的條件：

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

從圖1可知，隨著λ的降低，裝填的物品逐漸增加，直至等于背包載重14。第1次迭代時，λ等于λmax=2和λmin=0.3333的中間值1.1667，此時，由于物品1和4的單位重量價值均大于1.1667，物品1和4均裝入，故第1次迭代裝入物品的總重量為8。當迭代結束時，最優決策是[1，0.5，1，1]，最大價值是17。上述整個物品裝填過程及最終結果與貪心法中每次選取單位重量價值最大的物品裝包所對應的裝填過程和結果均一致。

3 結束語

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

參考文獻（References）：

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

出版社，2006.

[2] 陳慧南.數據結構與算法：C++語言描述[M].高等教育出版

社，2005.

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

Cambridge：Cambridge University Press，2004：1-244