5.動態(tài)規(guī)劃
????5.1 什么是動態(tài)規(guī)劃称簿？???
????5.2 自底向上的動態(tài)規(guī)劃：????
????5.3 自頂向下的動態(tài)規(guī)劃??
????5.4? 0-1背包問題：
????5.5 完全背包問題
5.動態(tài)規(guī)劃?
? ? 5.1 什么是動態(tài)規(guī)劃活箕？
????????動態(tài)規(guī)劃是?種把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法缭乘。
????????動態(tài)規(guī)劃對于子問題重疊的情況特別有效捏雌，因?yàn)樗鼘?問題的解保存在存儲空間中植袍，當(dāng)需要某個子問題的解時稿黍，直接取值即可
? ? 5.2 自底向上的動態(tài)規(guī)劃：
? ? 5.3 自頂向下的動態(tài)規(guī)劃
? ? 5.4? 0-1背包問題：
????????一個小偷面前有 n 個財寶镣衡，每個財寶有重量 w 和價值 v 兩種屬性暇番，而他的背包只能攜帶一定重量的財寶（c）嗤放，在已知所有財寶的重量和價值的情況下，如何選取財寶壁酬，可以最大限度的利用當(dāng)前的背包容量次酌，取得最大價值的財寶？（限定每種物品只有一個）
? ? ? ? 我們用 maxValue [i] [j]? 來表示當(dāng)前背包體積(j) 從(1,2,3, …i)件商品中選取最大價值的組合舆乔。
????????我們只考慮第 i 件商品岳服，第 i 件商品只有兩種情況，拿與不拿：
? ? ? ? (1)若第 i 個物品在最優(yōu)解中
? ??????我們直接最先將第 i 個物品其放入空背包中希俩，此時背包剩余體積為 j-w吊宋，物品還有1,2,…,i-1，我們需要從其中繼續(xù)找出最好的組合使得在背包體積為j-w且物品為1,2,…,i-1的情況下達(dá)到價值最高颜武。由此可知：
? ? ? ? maxValue [i] [j] =?maxValue [ i-1 ] [ j-w ] + v? ? ? ? ? ? ? ? ??
? ??????(2)若第 i 個物品不在最優(yōu)解中
????????maxValue [i] [j] =?maxValue [ i-1 ] [ j ]? ? ? ? ? ? ?
? ? ? ? 得出結(jié)論
????????maxValue [i] [j] = max{ maxValue [ i-1 ] [ j-w ] + v璃搜，maxValue [ i-1 ] [ j ]?}?
? ? 5.5 完全背包問題：
? ? ? ? 此時，每種物品數(shù)量為無限盒刚。
?????????(1)使用第 i 類物品
? ??????此時至少使用1個第 i 類物品腺劣。故而我們分析先用掉?1個第 i 類物品的情況： 此時背包剩余體積為 j-w?
????????maxValue [i] [j] =?maxValue [ i ] [ j-w ] + v? （注意：前后都是 i，而不是出現(xiàn) i-1因块，因?yàn)榉湃胍粋€還可以繼續(xù)放）? ? ? ? ? ? ? ? ??
?? ??????(2)不使用第 i 類物品
? ??????maxValue [i] [j] =?maxValue [ i-1 ] [ j ]??
