背包問題 －－ 2) 改進，自頂向下的動態編程

        在上一篇《背包問題 －－ 1) 思路，遞歸求解》中，我們討論了用遞歸的方式來解決背包問題。但是，直接使用遞歸會造成大量的重復運算，就上一篇中的例子來說，對于容積為17的背包來說，其中兩種組合方案為：

        方案一： 4(A) + 5(B) = 9 ，即背包中裝一個A物品和一個B物品；

        方案二： 5(B) + 10(C) = 15 ，即背包中裝一個B物品和一個C物品；

注意，上面兩種方案都需要計算knap(space = cap - item[1].size)（注：1對應B物品）的情況，這就造成了重復計算，而且計算量是成指數增長的。如果我們在第一次計算knap(space = cap - item[1].size)時就保存其返回值，那么在下一次需要用到的時候只需要直接使用這個返回值就行了，而不必再去計算。

        這里我們給出動態編程的定義，即遞歸程序中，在每一步遞歸調用前使用已計算的值來完成當前的遞歸調用。

        對于背包問題，我們用一個數組knowKnap[M]來保存每一個可能的space值。按動態編程改進后的程序源代碼如下：

posted on 2006-01-03 23:16 PIGWORLD 閱讀(4144) 評論(3)  編輯 收藏 引用