背包問(wèn)題的本質(zhì):

如果每件物品都要考慮是否放入背包所需的深度為n，最壞就需要O()的時(shí)間

而在考慮每件物品的過(guò)程中，中間有很多分支的計(jì)算是重復(fù)的，或者說(shuō)可以基于之前的運(yùn)算得到的子問(wèn)題答案簡(jiǎn)化本次的運(yùn)算量

因此空間換時(shí)間，開一個(gè)數(shù)組記錄中間的運(yùn)算過(guò)程，得到答案。

先展示一下原始時(shí)間復(fù)雜度比較差的思路：

不管如何，用測(cè)試數(shù)據(jù)也能返回正確結(jié)果。

接下來(lái)使用動(dòng)態(tài)規(guī)劃，不過(guò)第一次寫的時(shí)候，代碼規(guī)劃的稀爛：

不過(guò)總歸把表完整打出來(lái)了，而且和手算的結(jié)果一樣，說(shuō)明思路是沒(méi)問(wèn)題的，重點(diǎn)還是一個(gè)算新的數(shù)據(jù)要根據(jù)已經(jīng)算出的數(shù)據(jù)，就會(huì)簡(jiǎn)化一部分運(yùn)算。

不過(guò)實(shí)際應(yīng)用可能更需要的是展示具體的選擇和最終的結(jié)果，而且上面的寫法也太丑陋了，因此優(yōu)化一下：

其中找出所選的物品是根據(jù)結(jié)果和表格來(lái)逆向推導(dǎo)的，這次的代碼已經(jīng)簡(jiǎn)潔了不少。

不過(guò)，如果只是需要一個(gè)結(jié)果的話，觀察到表格中的下面一行都是根據(jù)上面一行得到的，開一個(gè)大二維數(shù)組似乎有點(diǎn)奢侈，所以用滾動(dòng)數(shù)組優(yōu)化一下：

當(dāng)然，也可以考慮在原始遞歸的思路上改進(jìn)，這樣的做優(yōu)點(diǎn)是看起來(lái)比較簡(jiǎn)單，也很好寫：

最后提醒一下數(shù)組記得初始化。