在上一篇《背包問題 －－ 1) 思路，遞歸求解》中，我們討論了用遞歸的方式來解決背包問題。但是，直接使用遞歸會造成大量的重復(fù)運算，就上一篇中的例子來說，對于容積為17的背包來說，其中兩種組合方案為：
方案一： 4(A) + 5(B) = 9 ，即背包中裝一個A物品和一個B物品；
方案二： 5(B) + 10(C) = 15 ，即背包中裝一個B物品和一個C物品；
注意，上面兩種方案都需要計算knap(space = cap - item[1].size)（注：1對應(yīng)B物品）的情況，這就造成了重復(fù)計算，而且計算量是成指數(shù)增長的。如果我們在第一次計算knap(space = cap - item[1].size)時就保存其返回值，那么在下一次需要用到的時候只需要直接使用這個返回值就行了，而不必再去計算。
這里我們給出動態(tài)編程的定義，即遞歸程序中，在每一步遞歸調(diào)用前使用已計算的值來完成當(dāng)前的遞歸調(diào)用。
對于背包問題，我們用一個數(shù)組knowKnap[M]來保存每一個可能的space值。按動態(tài)編程改進后的程序源代碼如下：
