動態(tài)規(guī)劃認(rèn)知
? 在問題滿足最優(yōu)性原理之后稠腊，用動態(tài)規(guī)劃解決問題的核心就在于填表认臊，表填寫完畢，最優(yōu)解也就找到。
01 背包
問題
有n件物品和一個容量為m的背包搔体，放入第ｉ件物品所需要的空間為ｗi恨樟，第ｉ件物品的價值為vｉ，問背包可以放入物品的最大價值為多少疚俱？
- 此問題不可用貪心算法劝术，貪心法得到的往往不是最優(yōu)解。
- 直接暴力窮舉n件物品，時間復(fù)雜度是O(2^n)养晋，效率過低衬吆，且存在大量重復(fù)運(yùn)算。
算法
? 綜上我們采用兩重循環(huán)的方式來解決此問題绳泉，避免了復(fù)雜的遞歸逊抡，并且采用數(shù)組存儲數(shù)據(jù)，使得計(jì)算次數(shù)大大減少零酪，復(fù)雜度由O(2^n)優(yōu)化到了O(VW)*冒嫡。
for(int i=1; i<=n; i++){ //物品
for(int j=V; j>=0; j--){ //容量
if(j >= w[i]) //放得下物品，使用狀態(tài)轉(zhuǎn)移方程
dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
else //放不下物品四苇，直接跳過孝凌，沿承 i-1 個物品的價值
dp[i][j] = dp[i-1][j];
}
}
優(yōu)化
空間優(yōu)化
? 實(shí)際上，二維數(shù)組的空間復(fù)雜度過高月腋，有時候也不現(xiàn)實(shí)蟀架，所以有時采用狀態(tài)壓縮，將二維數(shù)組壓縮至一維榆骚。
? 壓縮原理：實(shí)質(zhì)上片拍，i本身無實(shí)質(zhì)性意義，在第 i+1 次循環(huán)尚未開始之前寨躁，第 i 行已經(jīng)保存了當(dāng)前的數(shù)據(jù)穆碎，且 0 到 i-1 行就沒有使用價值了，故可以將二維數(shù)組壓縮為一維數(shù)組职恳，從后向前遍歷所禀，狀態(tài)轉(zhuǎn)移方程中的 [i-1] 就無存在價值了。
? 對于外層循環(huán)中的每一個 i 值放钦，其實(shí)都是不需要記錄的色徘，在第 i-1 次循環(huán)已結(jié)束且第 i 次循環(huán)未開始，dp數(shù)組還未更新時操禀，dp[j]還記錄著前 i-1 個物品在容量為 j 時的最大價值褂策，這樣就相當(dāng)于還記錄著 dp[i-1][j]和dp[i-1][j-vol[i]]+val[i]。
? 狀態(tài)轉(zhuǎn)移方程修改為 dp[j] = max(dp[j], dp[j - w[i]] + v[i])
恰好裝滿
如果要求恰好裝滿背包颓屑，那么在初始化時除了f[0]為0其它f[1..V]均設(shè)為-∞斤寂，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。
如果沒有要求必須把背包裝滿揪惦，而是只希望價格盡量大遍搞，初始化時應(yīng)該將f[0..V]全部設(shè)為0。 ——《背包九講》
? 可以將其理解為不能把背包填滿的解都是非法（價值小于零）的器腋，從而在計(jì)算中排除這些解溪猿」辰埽或者說當(dāng)前的合法解一定是從之前的合法狀態(tài)推得的。
? 這個技巧可以推廣到其他背包問題诊县，不僅僅限于01背包讲弄。
常數(shù)優(yōu)化
? 經(jīng)過圖表可知，并不需要將表中的數(shù)據(jù)全部算出依痊，只需要算一部分即可避除。因?yàn)樽詈笏蠼Y(jié)果為dp[n][v]，其在 n-1 行所需的最小的 j 為 v-w[n-1]抗悍，同理驹饺，對于第 i 行, j 最小循環(huán)至 v- sum{w[n...i-1]} ,綜上所述我們可以優(yōu)化第二層的循環(huán)次數(shù)，代碼如下：
//理論上的第二層循環(huán)
// bound=max{V-sum{w[i..n]},w[i]};
// for(int j=V;j>=bound;j--)
for(i = 1; i<=n; i++){//實(shí)際代碼
int sum = 0;
for(int k = i ; k <= n ; ++k){
sum += w[k];
lower = max(sum, w[i]);
for(j = V ; j >= lower; j--){
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
? 因?yàn)槿羰?V-sum{w[i..n]} < w[i] 的話缴渊，則無法取到第 **i **個物品了赏壹，所以就把下限定為 w[i]，進(jìn)一步減少第二層循環(huán)次數(shù)衔沼，這種方法在V很大的情況下會節(jié)省時間蝌借。
封裝
//kuangbin 和 《背包九講》 中都給出了這個代碼
//此處僅僅將第二層循環(huán)和數(shù)組封裝了，相當(dāng)于對一個物品進(jìn)行處理,但是未加入常數(shù)優(yōu)化
//但是在多重背包里會用到
void ZeroOnePack(int cost,int value){
for(int j = nValue ; j >= cost ; j??)
dp[i] = max(dp[i] , dp[i?cost] + value);
}
完全背包
問題
有N種物品和一個容量為V的背包指蚁，每種物品都有無限件可用菩佑。第i種物品的費(fèi)用是c[i]，價值是w[i]凝化。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量稍坯，且價值總和最大。
思考方向還是先從二維數(shù)組下手搓劫，得到轉(zhuǎn)移方程瞧哟，再向一維數(shù)組優(yōu)化
算法
此處采用和01背包相似的思考方式，01背包每個物品都拿一次枪向，所以對于同一個 i 下的 j 都應(yīng)該是獨(dú)立的勤揩，即每個 j 中至多包含一個當(dāng)前物品，所以由后向前遍歷秘蛔，但是01背包中陨亡，每個 i 不止用一次，可能用多次深员，所以偏大的 j 中的情況就不應(yīng)從i-1 那一行轉(zhuǎn)移负蠕，而應(yīng)該是從同一行中轉(zhuǎn)移，這樣才能保證可以出現(xiàn)多個 i
for(int i = 1; i <= n; i++) //正序
for(int j = 0; j <= V; j++){ //還是正序
if(j >= w[i]){ //放得下
dp[i][j] = max{dp[i-1][j] , dp[i][j-w[i]] + v[i];
} else{ //放不下
dp[i][j] = dp[i-1][j];
}
}
思維陷阱
背包問題其實(shí)有一個隱藏的條件倦畅，就是包的體積和物品的質(zhì)量其實(shí)都是整數(shù)遮糖，雖說是無限多的物品，但是實(shí)質(zhì)上還是枚舉出來了滔迈，在 i 行的遍歷一定能枚舉所有含 i 情況止吁。
完全背包每次做出選擇是取決于當(dāng)前這一步的，而01背包每次做出選擇是取決于上一步的燎悍。主要就是因?yàn)楫?dāng)前這一步一個物品放過以后敬惦，表格逐漸向右填寫，隨著可放空間的增加谈山，可以判斷這一步是否還可以再放一個當(dāng)前的物品俄删。
優(yōu)化
空間優(yōu)化
和01背包一樣，二維數(shù)組太過浪費(fèi)空間奏路，可以采用一維滾動數(shù)組的方式來減少空間開銷畴椰。
轉(zhuǎn)移方程可化為 dp[j] = max{ dp[j] , dp[j-w[i]] + v[i] }
常數(shù)優(yōu)化
值得一提的是，上面的偽代碼中兩層 for 循環(huán)的次序可以顛倒鸽粉。這個結(jié)論有可能會帶來算法時間常數(shù)上的優(yōu)化斜脂。
封裝
//依舊是沒有常數(shù)優(yōu)化
//完全背包，代價為 cost, 獲得的價值為 value触机，也是對一個物品的處理
void CompletePack(int cost,int value){
for(int i = cost;i <= nValue;i++)
dp[i]=max(dp[i] , dp[i?cost] + value);
}
多重背包
問題
有N種物品和一個容量為V的背包帚戳。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]儡首，價值是w[i]片任。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價值總和最大蔬胯。
算法
我們在此考慮將多重背包轉(zhuǎn)化為01背包和完全背包对供。
- 正如在完全背包中探討的一樣，所謂“無限”只是相對無限氛濒，即背包里全部放這個東西也無法全部將其放下時产场，就可以認(rèn)為是無限了。
- 根據(jù)此方法泼橘，剩下的所謂有限的涝动，就可以拆分成多個物品，根據(jù)01背包來計(jì)算炬灭。但是如果拆分成 n[i] ** 個效率就太低了醋粟，所以采用二進(jìn)制優(yōu)化這個問題。 使這些系數(shù)分別為1 , 2, 4 , ... , 2^(k-1) , n[i]-2^k+1 重归，且k是滿足n[i]-2^k+1>0的最大整數(shù)米愿。 這是因?yàn)檫@些數(shù)之和為n[i]** , 這樣就將 n[i]個物品優(yōu)化到了 log( n[i] ) 個，提高了效率鼻吮。
- 此問題可以用單調(diào)隊(duì)列優(yōu)化至 O(VM)育苟，即和前兩種問題一樣，但是太過復(fù)雜椎木，日后補(bǔ)充违柏。
?
void MultiplePack(int cost,int value,int amount){ //花費(fèi)博烂， 價值 ， 數(shù)量
if(cost*amount>=V) //相對“無限”
CompletePack(cost,value); //完全背包
else{
int k=1;
while(k < amount){
ZeroOnePack(k*cost,k*value); //系數(shù)遞增漱竖，1禽篱，2，4馍惹，8躺率，...
amount?=k;
k<<=1; //k左移一位，即k*=2
}
ZeroOnePack(amount*cost,amount*value);//這個不要忘記了万矾，這是最后一個系數(shù)悼吱，即n[i]減去之前所有系數(shù)的結(jié)果
}
}
(待思考)一種實(shí)現(xiàn)較為簡單的O(V N) 復(fù)雜度解多重背包問題的算法×急罚基本思想是這樣的：設(shè)F[i; j] 表示“用了前i 種物品填滿容量為j 的背包后后添，最多還剩下幾個第i 種物品可用”，如果F[i, j] = -1 則說明這種狀態(tài)不可行们颜，若可行應(yīng)滿足0 ≤ F[i,j] ≤ Mi吕朵。
混合三種背包
問題
有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包）窥突，有的物品可以取的次數(shù)有一個上限（多重背包）努溃。應(yīng)該怎么求解呢
算法
for i=1..N
if 第i件物品屬于01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品屬于完全背包
CompletePack(c[i],w[i])
else if 第i件物品屬于多重背包
MultiplePack(c[i],w[i],n[i])
評價
真的就這么簡單粗暴，不過也體現(xiàn)了模塊化之后的便利之處阻问。(kuangbin模板中甚至都沒有提到這個問題)
二維費(fèi)用的背包問題
問題
對于每件物品梧税，具有兩種不同的費(fèi)用；選擇這件物品必須同時付出這兩種代價称近；對于每種代價都有一個可付出的最大值（背包容量）第队。問怎樣選擇物品可以得到最大的價值。設(shè)這兩種代價分別為代價1和代價2刨秆，第i件物品所需的兩種代價分別為a[i]和b[i]凳谦。兩種代價可付出的最大值（兩種背包容量）分別為A和B。物品的價值為v[i]衡未。
算法
費(fèi)用增加一維尸执，其實(shí)只需將狀態(tài)加一維即可。設(shè) f[i][v][u] 表示前i件物品付出兩種代價分別為 v 和 u 時可獲得的最大值缓醋。狀態(tài)轉(zhuǎn)移方程
f[i][w][u] = max{ f[i-1][w][u] 如失，f[i-1][w-a[i]][u-b[i]] +w[i]}
===TO BE CONTINUE==
?
