動態規劃算法的三式融合教學法案例研究

吳清壽，郭磊

（武夷學院數學與計算機學院，武夷山 354300）

1 問題概述

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

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

文獻[3]從培養學生算法思維和提高應用能力的角度提出了教學改革措施。文獻[4]從多個實例中抽象出動態規劃算法的特征。文獻[5]用改進的動態規劃算法解決了背包問題。上述文獻從不同的角度對動態規劃算法進行了研究，但未對學生如何更好掌握算法提出解決方法。

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

2 三式融合教學法

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

從上述基本思想中可以看出，適用于動態規劃法求解的問題通常具有重復子問題性質和最優子結構性質。利用重復子問題性質，解決了冗余計算問題，而最優子結構性質確保問題求解的每一步驟都包含了子問題的最優解。

基于以上基本思想，以0-1背包問題的求解過程為例，采用三式融合方法，給出問題求解步驟，推導出問題的遞歸關系式，將求解過程圖表化，從而自然得到算法的實現代碼。

三式融合教學法包含公式歸納，表格填充和代碼編寫三個部分。下面對三種方法予以介紹，并在下一章中結合具體的案例進行分析。

（1）公式是本質。動態規劃法中，利用重復子問題性質和最優子結構性質可以定義解的遞歸公式，但解決一個新問題的遞歸公式的提出并不是顯而易見的，需要通過對問題進行具體的分析之后再予以總結歸納而得出。

（2）圖表是手段。公式刻畫了問題的本質，但求解過程仍然是抽象的。通過圖表的形式將求解過程具象化，能夠加深學生對問題的理解，獲得對問題的形象認知，進而對新問題能夠舉一反三，達到掌握算法的求解方法及本質特征的效果。

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

在實際教學過程中，三者不是獨立的，而是根據問題的特征，將三種方法交替使用，有機融合，讓學生在逐步分析問題的過程中掌握算法。

3 實例分析

本文以動態規劃解0-1背包問題為例。

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

為了填充表格，先設一個二維數組m[i][j]，i（1<=i<=5）表示第i個物品，j（0<=j<=10）表示背包的當前容量，m[i][j]表示當背包容量為j時裝入前i個物品產生的最大價值。

步驟一：首先考慮當背包的容量為0時，此時無法裝入任何物品，則產生的價值為0，可以得到公式（1）：

填充結果見表1中的第0列。

可用代碼描述如下：

步驟二：考慮第一個物品的裝入問題，設背包的容量為c，當c小于w1，此時物品不能放入背包，產生的價值為0，從而得到公式（2）：

表格填充情況見表1中的m[1][1]～m[1][3]。

可用代碼描述如下：

當背包容量等于或大于w1時，物品可以放入背包，則產生的價值為v1。因為當前只有一個物品，背包中物品的最大價值為v1。得到公式（3）：

表格填充情況見表1中的m[1][4]～m[1][10]。

對應代碼如下：

步驟三：現在考慮有兩個物品的情況，當背包剩余容量c

表格填充情況見表1中的m[2][1]～m[2][4]。

對應代碼如下：

當背包容量c>=w2時，第二個物品可以放入背包，也可以不放入，這需要根據是否能產生當前最優價值來決定。若物品2放入，產生價值v2，其對應的背包總價值應當為前一步驟中未放入w2前對應的背包（其容量為c-w2）中物品的總價值與v2之和，即m[i-1][cw2]+v2。若物品2不放入，則當前的總價值為步驟二中對應的背包（其容量為c）中物品價值的最優值m[1][c]，取兩者最大值作為當前容量下背包中的最大價值。由此，得到公式（5）：

表格填充情況見表1中的m[2][5]～m[2][10]。

對應代碼如下：

以m[2][8]的填充為例。當背包容量為8時，背包容量小于前兩個物品的重量之和，則只能選擇一個，第一個物品的價值大于第二個物品價值，所以選擇將第一個物品裝入背包，背包中的物品價值為6。其實際計算過程是m[1][c-w2]+v2=m[1][8-5]+v2=m[1][3]+4=0+4=4，可以看出，m[1][3]處未產生價值，即未裝入物品1，所以此處只裝入物品2。m[1][c]=m[1][8]=6，表示裝入物品1，產生價值為6，所以應選擇6作為當前背包的物品總價值。

步驟四：當n>i>2時，其計算過程與步驟2相同，可得到通用公式：

表格填充情況見表1中的第3第4行。

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

步驟五：當i=n時，因為m[i][c]的值只與m[i-1][c]的值相關，所以此時無需完整計算整個過程，只需根據公式（7）計算c=C時的m[n][C]即可。

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

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

表1 0-1背包問題各步驟最優值

由最優值構建最優解的過程較為簡單，從m[n][C]開始搜索，如果m[i][c]>m[i-1][c]，說明在容量為c時，對于第i個物品，將其放入背包中將得到當前的最優解，則令xi=1，并縮小背包容量為c-wi，繼續對i-1個物品的放入情況即m[i-1][c-wi]進行檢查，構造最優解。如果m[i][c]==m[i-1][c]，說明放入第i個物品無法產生新的更優的解，則第i個物品不構成最優解，令xi=0，并由m[i-1][c]繼續構造最優解。重復以上過程。當i等于1時，考慮構建最優值的步驟二中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]為最優解的求解順序，其單元格右上角括號中的值即為 xi的值，可以看出 x={1，0，0，1，1}，即選擇物品 1，4，5，背包中的物品價值最大。

4 結語

從近幾年的教學情況可以看到，通過三式融合的教學方法，可以有效地幫助學生理解算法的基本思想，全面掌握算法的執行情況，并能較容易的將分析過程轉化為程序代碼，提升了學生的實踐動手能力。另外，學生可以通過這種方法對比用不同算法解決同一問題的優缺點，進而提出算法的改進措施，并能將其應用到新的問題上。