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