吳清壽，郭磊

（武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，武夷山 354300）

1 問(wèn)題概述

《算法設(shè)計(jì)與分析》課程是計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的核心課程，教學(xué)過(guò)程涉及算法基本思想的理解、算法的設(shè)計(jì)模式、算法的特性和算法的效率等環(huán)節(jié)，關(guān)聯(lián)的前導(dǎo)課程較多，要求學(xué)生具備較好的基礎(chǔ)知識(shí)和較強(qiáng)的分析能力。而與課程地位相悖的卻是課時(shí)的大量壓縮，現(xiàn)在各高校對(duì)本課程的課時(shí)安排一般都少于40節(jié)[1]，筆者所在學(xué)校對(duì)本課程的課時(shí)安排是32+8，即32節(jié)理論講解加上8課時(shí)的上機(jī)實(shí)踐。課時(shí)量不足與課程內(nèi)容較高的復(fù)雜度兩者之間的不均衡給教學(xué)造成了困難：知識(shí)點(diǎn)抽象層次較高，囿于課時(shí)無(wú)法深入分析；需要大量的實(shí)踐鞏固對(duì)算法思想的理解，但實(shí)踐課時(shí)通常很少甚至沒(méi)有；學(xué)生普遍缺乏將理論內(nèi)化為編程思想的能力。

動(dòng)態(tài)規(guī)劃法是《算法設(shè)計(jì)與分析》課程的重要章節(jié)，也是歷屆學(xué)生普遍反映較難理解的內(nèi)容。本章節(jié)內(nèi)容除了具有課程本身的教學(xué)難處之外，其教學(xué)難點(diǎn)還體現(xiàn)在以下幾個(gè)方面：一是對(duì)算法的最優(yōu)子結(jié)構(gòu)性質(zhì)理解存在困難。不同問(wèn)題，其最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法都不同，這是學(xué)習(xí)算法過(guò)程中的主要障礙。二是對(duì)算法的運(yùn)行過(guò)程難以理解。動(dòng)態(tài)規(guī)劃算法通常以遞歸的方式定義其子問(wèn)題的最優(yōu)解，而遞歸方法在思想上易于理解，但其執(zhí)行過(guò)程的分析存在較大的難度。三是無(wú)法做到學(xué)以致用[2]。學(xué)生可以通過(guò)課堂學(xué)習(xí)掌握相關(guān)例子的求解方法，但針對(duì)新的問(wèn)題難以提出有效的算法過(guò)程。究其原因，主要是對(duì)算法的思想理解不透徹，對(duì)算法解決具體問(wèn)題的過(guò)程掌握不清楚造成的。

文獻(xiàn)[3]從培養(yǎng)學(xué)生算法思維和提高應(yīng)用能力的角度提出了教學(xué)改革措施。文獻(xiàn)[4]從多個(gè)實(shí)例中抽象出動(dòng)態(tài)規(guī)劃算法的特征。文獻(xiàn)[5]用改進(jìn)的動(dòng)態(tài)規(guī)劃算法解決了背包問(wèn)題。上述文獻(xiàn)從不同的角度對(duì)動(dòng)態(tài)規(guī)劃算法進(jìn)行了研究，但未對(duì)學(xué)生如何更好掌握算法提出解決方法。

結(jié)合學(xué)生的實(shí)際情況，提出一種合理有效的教學(xué)方法，對(duì)學(xué)生掌握動(dòng)態(tài)規(guī)劃算法的基本思想、基本性質(zhì)及其在具體問(wèn)題上的分析方法是一件有必要有意義的工作。為此，筆者在多年教學(xué)《算法設(shè)計(jì)與分析》課程的過(guò)程中，提出了一種“三式融合”的教學(xué)模式，旨在促進(jìn)學(xué)生把握問(wèn)題本質(zhì)，理解算法思想，提升實(shí)踐能力，做到學(xué)以致用。

2 三式融合教學(xué)法

要掌握動(dòng)態(tài)規(guī)劃算法，首先要掌握其基本思想[6]。將原問(wèn)題分解為相應(yīng)的子問(wèn)題是分治法和動(dòng)態(tài)規(guī)劃法的共同思路，而子問(wèn)題是重復(fù)的還是相互獨(dú)立的決定了算法的選擇問(wèn)題。為了便于后續(xù)更大規(guī)模問(wèn)題的求解，動(dòng)態(tài)規(guī)劃法通過(guò)引入填表法（或者稱備忘錄）記錄每個(gè)子問(wèn)題的最優(yōu)解。先從極小的（即可直接求解的）子問(wèn)題開(kāi)始，將其解填充到備忘錄。逐步擴(kuò)大問(wèn)題規(guī)模，當(dāng)前問(wèn)題與子問(wèn)題性質(zhì)相同，可通過(guò)查子問(wèn)題的解構(gòu)造當(dāng)前問(wèn)題的解，提高了算法效率，避免了子問(wèn)題的重復(fù)求解過(guò)程。

從上述基本思想中可以看出，適用于動(dòng)態(tài)規(guī)劃法求解的問(wèn)題通常具有重復(fù)子問(wèn)題性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。利用重復(fù)子問(wèn)題性質(zhì)，解決了冗余計(jì)算問(wèn)題，而最優(yōu)子結(jié)構(gòu)性質(zhì)確保問(wèn)題求解的每一步驟都包含了子問(wèn)題的最優(yōu)解。

基于以上基本思想，以0-1背包問(wèn)題的求解過(guò)程為例，采用三式融合方法，給出問(wèn)題求解步驟，推導(dǎo)出問(wèn)題的遞歸關(guān)系式，將求解過(guò)程圖表化，從而自然得到算法的實(shí)現(xiàn)代碼。

三式融合教學(xué)法包含公式歸納，表格填充和代碼編寫(xiě)三個(gè)部分。下面對(duì)三種方法予以介紹，并在下一章中結(jié)合具體的案例進(jìn)行分析。

（1）公式是本質(zhì)。動(dòng)態(tài)規(guī)劃法中，利用重復(fù)子問(wèn)題性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)可以定義解的遞歸公式，但解決一個(gè)新問(wèn)題的遞歸公式的提出并不是顯而易見(jiàn)的，需要通過(guò)對(duì)問(wèn)題進(jìn)行具體的分析之后再予以總結(jié)歸納而得出。

（2）圖表是手段。公式刻畫(huà)了問(wèn)題的本質(zhì)，但求解過(guò)程仍然是抽象的。通過(guò)圖表的形式將求解過(guò)程具象化，能夠加深學(xué)生對(duì)問(wèn)題的理解，獲得對(duì)問(wèn)題的形象認(rèn)知，進(jìn)而對(duì)新問(wèn)題能夠舉一反三，達(dá)到掌握算法的求解方法及本質(zhì)特征的效果。

（3）代碼是目的。算法的理解是前提條件，但最終還需將其轉(zhuǎn)化為程序代碼，獲得從分析問(wèn)題到解決問(wèn)題的能力，這是提出三式融合教學(xué)法的主要目的。利用公式抽象問(wèn)題的本質(zhì)，利用圖表表征公式的求解步驟，依據(jù)表格的填充過(guò)程及方法，模擬出程序代碼，大大降低了程序設(shè)計(jì)的難度，且程序執(zhí)行結(jié)果易于驗(yàn)證，讓學(xué)生從中獲得編程的樂(lè)趣，并系統(tǒng)掌握程序設(shè)計(jì)的方法。

在實(shí)際教學(xué)過(guò)程中，三者不是獨(dú)立的，而是根據(jù)問(wèn)題的特征，將三種方法交替使用，有機(jī)融合，讓學(xué)生在逐步分析問(wèn)題的過(guò)程中掌握算法。

3 實(shí)例分析

本文以動(dòng)態(tài)規(guī)劃解0-1背包問(wèn)題為例。

案例數(shù)據(jù)：n=5，C=10，w={4，5，6，2，2}，v={6，4，5，3，6}，表示有5個(gè)物品，w表示第i個(gè)物品的重量，vi表示第i個(gè)物品的價(jià)值，1<=i<=5，C表示背包的容量。這是一個(gè)0-1背包問(wèn)題，物品不能分割后裝入背包，只能選擇整個(gè)放入或不放入。目標(biāo)：要求裝入背包中的物品的總價(jià)值最大。

為了填充表格，先設(shè)一個(gè)二維數(shù)組m[i][j]，i（1<=i<=5）表示第i個(gè)物品，j（0<=j<=10）表示背包的當(dāng)前容量，m[i][j]表示當(dāng)背包容量為j時(shí)裝入前i個(gè)物品產(chǎn)生的最大價(jià)值。

步驟一：首先考慮當(dāng)背包的容量為0時(shí)，此時(shí)無(wú)法裝入任何物品，則產(chǎn)生的價(jià)值為0，可以得到公式（1）：

填充結(jié)果見(jiàn)表1中的第0列。

可用代碼描述如下：

步驟二：考慮第一個(gè)物品的裝入問(wèn)題，設(shè)背包的容量為c，當(dāng)c小于w1，此時(shí)物品不能放入背包，產(chǎn)生的價(jià)值為0，從而得到公式（2）：

表格填充情況見(jiàn)表1中的m[1][1]～m[1][3]。

可用代碼描述如下：

當(dāng)背包容量等于或大于w1時(shí)，物品可以放入背包，則產(chǎn)生的價(jià)值為v1。因?yàn)楫?dāng)前只有一個(gè)物品，背包中物品的最大價(jià)值為v1。得到公式（3）：

表格填充情況見(jiàn)表1中的m[1][4]～m[1][10]。

對(duì)應(yīng)代碼如下：

步驟三：現(xiàn)在考慮有兩個(gè)物品的情況，當(dāng)背包剩余容量c

表格填充情況見(jiàn)表1中的m[2][1]～m[2][4]。

對(duì)應(yīng)代碼如下：

當(dāng)背包容量c>=w2時(shí)，第二個(gè)物品可以放入背包，也可以不放入，這需要根據(jù)是否能產(chǎn)生當(dāng)前最優(yōu)價(jià)值來(lái)決定。若物品2放入，產(chǎn)生價(jià)值v2，其對(duì)應(yīng)的背包總價(jià)值應(yīng)當(dāng)為前一步驟中未放入w2前對(duì)應(yīng)的背包（其容量為c-w2）中物品的總價(jià)值與v2之和，即m[i-1][cw2]+v2。若物品2不放入，則當(dāng)前的總價(jià)值為步驟二中對(duì)應(yīng)的背包（其容量為c）中物品價(jià)值的最優(yōu)值m[1][c]，取兩者最大值作為當(dāng)前容量下背包中的最大價(jià)值。由此，得到公式（5）：

表格填充情況見(jiàn)表1中的m[2][5]～m[2][10]。

對(duì)應(yīng)代碼如下：

以m[2][8]的填充為例。當(dāng)背包容量為8時(shí)，背包容量小于前兩個(gè)物品的重量之和，則只能選擇一個(gè)，第一個(gè)物品的價(jià)值大于第二個(gè)物品價(jià)值，所以選擇將第一個(gè)物品裝入背包，背包中的物品價(jià)值為6。其實(shí)際計(jì)算過(guò)程是m[1][c-w2]+v2=m[1][8-5]+v2=m[1][3]+4=0+4=4，可以看出，m[1][3]處未產(chǎn)生價(jià)值，即未裝入物品1，所以此處只裝入物品2。m[1][c]=m[1][8]=6，表示裝入物品1，產(chǎn)生價(jià)值為6，所以應(yīng)選擇6作為當(dāng)前背包的物品總價(jià)值。

步驟四：當(dāng)n>i>2時(shí)，其計(jì)算過(guò)程與步驟2相同，可得到通用公式：

表格填充情況見(jiàn)表1中的第3第4行。

代碼與步驟三相似，此處略。

步驟五：當(dāng)i=n時(shí)，因?yàn)閙[i][c]的值只與m[i-1][c]的值相關(guān)，所以此時(shí)無(wú)需完整計(jì)算整個(gè)過(guò)程，只需根據(jù)公式（7）計(jì)算c=C時(shí)的m[n][C]即可。

則 m[n][C]=max（15，11）=15

由上述步驟得到的完整表格如表1所示。

表1 0-1背包問(wèn)題各步驟最優(yōu)值

由最優(yōu)值構(gòu)建最優(yōu)解的過(guò)程較為簡(jiǎn)單，從m[n][C]開(kāi)始搜索，如果m[i][c]>m[i-1][c]，說(shuō)明在容量為c時(shí)，對(duì)于第i個(gè)物品，將其放入背包中將得到當(dāng)前的最優(yōu)解，則令xi=1，并縮小背包容量為c-wi，繼續(xù)對(duì)i-1個(gè)物品的放入情況即m[i-1][c-wi]進(jìn)行檢查，構(gòu)造最優(yōu)解。如果m[i][c]==m[i-1][c]，說(shuō)明放入第i個(gè)物品無(wú)法產(chǎn)生新的更優(yōu)的解，則第i個(gè)物品不構(gòu)成最優(yōu)解，令xi=0，并由m[i-1][c]繼續(xù)構(gòu)造最優(yōu)解。重復(fù)以上過(guò)程。當(dāng)i等于1時(shí)，考慮構(gòu)建最優(yōu)值的步驟二中m[1][c]只有兩種取值：0 和 v1，所以，只要判斷 m[1][c]>0，則 x1=1，否則x1=0。表 1 中的 m[5][10]，m[4][8]，m[3][6]，m[2][6]，m[1][6]為最優(yōu)解的求解順序，其單元格右上角括號(hào)中的值即為 xi的值，可以看出 x={1，0，0，1，1}，即選擇物品 1，4，5，背包中的物品價(jià)值最大。

4 結(jié)語(yǔ)

從近幾年的教學(xué)情況可以看到，通過(guò)三式融合的教學(xué)方法，可以有效地幫助學(xué)生理解算法的基本思想，全面掌握算法的執(zhí)行情況，并能較容易的將分析過(guò)程轉(zhuǎn)化為程序代碼，提升了學(xué)生的實(shí)踐動(dòng)手能力。另外，學(xué)生可以通過(guò)這種方法對(duì)比用不同算法解決同一問(wèn)題的優(yōu)缺點(diǎn)，進(jìn)而提出算法的改進(jìn)措施，并能將其應(yīng)用到新的問(wèn)題上。