我在進行一些互聯(lián)網(wǎng)公司的技術筆試的時候，對于我來說最大的難題莫過于最后的那幾道編程題了酪呻，這對算法和數(shù)據(jù)結構有一定程度上的要求减宣，而“動態(tài)規(guī)劃”又是編程題中經(jīng)常出現(xiàn)的算法類型，并且對于我這種沒有搞過ACM競賽的菜鳥來說玩荠，那更是非常難受蚪腋。以至于很難通過筆試，所以打算好好的學習一下“動態(tài)規(guī)劃”這個部分姨蟋，就找到了動態(tài)規(guī)劃的經(jīng)典入門屉凯，背包9講來學習和參考。背包9講在網(wǎng)上也是有一定影響力的文章眼溶，是崔添翼大神的作品悠砚。我將分3 次，一次三講堂飞，對文章中我認為可能不好理解的部分灌旧，再具體化一些并把實現(xiàn)代碼發(fā)布上來。
進入主題吧
1 01背包問題
1.1 題目
有N 件物品和一個容量為V 的背包绰筛。放入第i 件物品耗費的費用是Ci枢泰，得到的價值是Wi。求解將哪些物品裝入背包可使價值總和最大铝噩。
1.2 基本思路
這是最基礎的背包問題衡蚂，特點是：每種物品僅有一件，可以選擇放或不放骏庸。用子問題定義狀態(tài)：即F[i; v] 表示前i 件物品恰放入一個容量為v 的背包可以獲得的最大價值毛甲。則其狀態(tài)轉移方程便是：
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的具被。所以有必要將它詳細解釋一下：“將前i 件物品放入容量為v 的背包中”這個子問題玻募，若只考慮第i 件物品的策略（放或不放），那么就可以轉化為一個只和前i - 1 件物品相關的問題一姿。如果不放第i 件物品七咧，那么問題就轉化為“前i -1 件物品放入容量為v 的背包中”，價值為F[i - 1; v]叮叹；如果放第i 件物品艾栋，那么問題就轉化為“前i - 1 件物品放入剩下的容量為v - Ci 的背包中”，此時能獲得的最大價值就是F[i - 1; v - Ci] 再加上通過放入第i 件物品獲得的價值Wi衬横。
偽代碼如下：
C++代碼實現(xiàn)：
#include <iostream>
using namespace std;
const int W=10000;
const int N=100;
int dp_1[N+1][W+1];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,w;
cin>>n>>w;
int *w1=new int [n];
int *v=new int [n];
int i;
for(i=0;i<n;i++)
{
cin>>w1[i]>>v[i];
}
for(i=0;i<w;i++)
{
if(i>=w1[0])
{
dp_1[0][i]=v[0];
}
else
{
dp_1[0][i]=0;
}
}
for(i=1;i<n;i++)
{
for(int j=0;j<=w;j++)
{
if(j>=w1[i])
{
dp_1[i][j]=max(dp_1[i-1][j],dp_1[i-1][j-w1[i]]+v[i]);
}
else
{
dp_1[i][j]=dp_1[i-1][j];
}
}
}
delete [] w1;
delete [] v;
cout<<dp_1[n-1][w]<<endl;
return 0;
}
1.3 優(yōu)化空間復雜度
以上方法的時間和空間復雜度均為O(V N)裹粤，其中時間復雜度應該已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O(V )。先考慮上面講的基本思路如何實現(xiàn)遥诉，肯定是有一個主循環(huán)i ←1 ...N拇泣，每次算出來二維數(shù)組F[i,0... V ] 的所有值。那么矮锈，如果只用一個數(shù)組F[0 ... V ]霉翔，能不能保證第i次循環(huán)結束后F[v] 中表示的就是我們定義的狀態(tài)F[i,v] 呢？F[i,v] 是由F[i - 1, v] 和F[i - 1, v - Ci] 兩個子問題遞推而來苞笨，能否保證在推F[i, v] 時（也即在第i 次主循環(huán)中推F[v] 時）能夠取用F[i - 1, v] 和F[i - 1, v - Ci] 的值呢债朵？事實上，這要求在每次主循環(huán)中我們以v ←V ... 0 的遞減順序計算F[v]瀑凝，這樣才能保證計算F[v] 時F[v -Ci] 保存的是狀態(tài)F[i - 1; v - Ci] 的值序芦。偽代碼如下：
C++代碼實現(xiàn)：
#include <iostream>
using namespace std;
const int W=10000;
int dp[W+1];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n,w;
cin>>n>>w;
int i,j,wi,pi;
for(i=0;i<n;i++)
{
cin>>wi>>pi;
if(i==0)
{
for(j=0;j<=w;j++)
{
if(j>=wi)
{
dp[j]=pi;
}
else
{
dp[j]=0;
}
}
}
else
{
for(j=w;j>=wi;j--)
{
dp[j]=max(dp[j],dp[j-wi]+pi);
}
}
}
cout<<dp[w]<<endl;
return 0;
}
其中的F[v] =max｛fF[v], F[v - Ci] +Wi｝ 一句，恰就對應于我們原來的轉移方程粤咪，因為現(xiàn)在的F[v - Ci] 就相當于原來的F[i - 1, v - Ci]谚中。如果將v 的循環(huán)順序從上面的逆序改成順序的話，那么則成了F[i, v] 由F[i, v - Ci] 推導得到寥枝，與本題意不符宪塔。
對于為什么需要逆序從v到0遍歷而不是從0到v遍歷，我們來舉例子具體化的說明一下
而如果逆序的話囊拜，你會發(fā)現(xiàn)F數(shù)組當前索引的值的計算依賴于前面索引的值某筐，不會使用到被更新過的值。這樣F數(shù)組就能在i-1的情況下完成i趟遍歷的更新冠跷。
------下面回歸文章主線------
事實上南誊，使用一維數(shù)組解01 背包的程序在后面會被多次用到，所以這里抽象出一個處理一件01 背包中的物品過程蔽莱，以后的代碼中直接調(diào)用不加說明弟疆。
有了這個過程以后，01 背包問題的偽代碼就可以這樣寫：
1.4 初始化的細節(jié)問題
我們看到的求最優(yōu)解的背包問題題目中盗冷，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優(yōu)解同廉，有的題目則并沒有要求必須把背包裝滿仪糖。一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。如果是第一種問法迫肖，要求恰好裝滿背包锅劝，那么在初始化時除了F[0] 為0，其它F[1...V ] 均設為-∞蟆湖，這樣就可以保證最終得到的F[V ] 是一種恰好裝滿背包的最優(yōu)解故爵。如果并沒有要求必須把背包裝滿，而是只希望價格盡量大隅津，初始化時應該將F[0...V ]全部設為0诬垂。
這是為什么呢劲室？可以這樣理解：初始化的F 數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿结窘，那么此時只有容量為0 的背包可以在什么也不裝且價值為0 的情況下被“恰好裝滿”很洋，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)隧枫，應該被賦值為-∞ 了喉磁。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”官脓，這個解的價值為0协怒，所以初始時狀態(tài)的值也就全部為0了。這個小技巧完全可以推廣到其它類型的背包問題卑笨，后面不再對進行狀態(tài)轉移之前的初始化進行講解孕暇。
1.5 一個常數(shù)優(yōu)化
上面?zhèn)未a中的
for i 1 to N
for v V to Ci
中第二重循環(huán)的下限可以改進。它可以被優(yōu)化為
這個優(yōu)化之所以成立的原因請讀者自己思考湾趾。（提示：使用二維的轉移方程思考較易芭商。）
我表示還沒想到，請各位大神看到這里幫忙解答一下搀缠。
1.6 小結
01 背包問題是最基本的背包問題铛楣，它包含了背包問題中設計狀態(tài)、方程的最基本思想艺普。另外，別的類型的背包問題往往也可以轉換成01 背包問題求解歧譬。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉移方程的意義瑰步，以及空間復雜度怎樣被優(yōu)化。
2 完全背包問題
2.1 題目
有N 種物品和一個容量為V 的背包缩焦，每種物品都有無限件可用读虏。放入第i 種物品的費用是Ci，價值是Wi袁滥。求解：將哪些物品裝入背包盖桥，可使這些物品的耗費的費用總和不超過背包容量，且價值總和最大题翻。
2.2 基本思路
這個問題非常類似于01 背包問題揩徊，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種塑荒，而是有取0 件熄赡、取1 件、取2
件……直至取?V /Ci? 件等許多種袜炕。如果仍然按照解01 背包時的思路本谜，令F[i; v] 表示前i 種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉移方程偎窘，像這樣：
這跟01 背包問題一樣有O(V N) 個狀態(tài)需要求解乌助，但求解每個狀態(tài)的時間已經(jīng)不是常數(shù)了，求解狀態(tài)F[i,v] 的時間是O(v/Ci)，總的復雜度可以認為是O(NV ∑ V/Ci)，是比較大的祸憋。將01 背包問題的基本思路加以改進，得到了這樣一個清晰的方法赏参。這說明01 背包問題的方程的確是很重要，可以推及其它類型的背包問題沿盅。但我們還是要試圖改進這個復雜度把篓。
2.3 一個簡單有效的優(yōu)化
完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i腰涧、j 滿足Ci ≤ Cj且Wi ≥ Wj韧掩，則將可以將物品j 直接去掉，不用考慮窖铡。這個優(yōu)化的正確性是顯然的：任何情況下都可將價值小費用高的j 換成物美價廉的i疗锐，得到的方案至少不會更差。對于隨機生成的數(shù)據(jù)滑臊，這個方法往往會大大減少物品的件數(shù)雇卷，從而加快速度颠猴。然而這個并不能改善最壞情況的復雜度，因為有可能特別設計的數(shù)據(jù)可以一件物品也去不掉氧映。
這個優(yōu)化可以簡單的O(N^2) 地實現(xiàn)，一般都可以承受振峻。另外扣孟，針對背包問題而言凤价，比較不錯的一種方法是：首先將費用大于V 的物品去掉利诺，然后使用類似計數(shù)排序的做法慢逾，計算出費用相同的物品中價值最高的是哪個侣滩，可以O(V + N) 地完成這個優(yōu)化君珠。這個不太重要的過程就不給出偽代碼了葛躏，希望你能獨立思考寫出偽代碼或程序舰攒。
O(N^2) 優(yōu)化部分代碼：
就是先將數(shù)值賦值到一個數(shù)組，然后進行比較處理掉不符合規(guī)則的數(shù)值芬骄，再重新賦值到另一個數(shù)組中去账阻。
int main()
{
int n,w;
cin>>n>>w;
int *w1=new int [n];
int *v=new int [n];
int i,wi,vi;
for(i=0;i<n;i++)
{
cin>>wi>>vi;
w1[i]=wi;
v[i]=vi;
}
int j;
int len=n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(w1[i]>w1[j]&&v[i]<=v[j]||w1[i]>w)
{
w1[i]=-1;
v[i]=-1;
len--;
}
}
}
cout<<"after delete"<<endl;
int *w2=new int [len];
int *v2=new int [len];
for(i=0,j=0;i<n;i++)
{
if(w1[i]!=-1)
{
w2[j]=w1[i];
v2[j]=v[i];
j++;
}
}
delete [] w1;
delete [] v;
for(i=0;i<len;i++)
{
cout<<w2[i]<<" "<<v2[i]<<endl;
}
return 0;
}
O(V + N)優(yōu)化部分代碼：
就首先將讀入的數(shù)值以key(體積) value(價值)的形式存入map中姻僧，然后不斷更新map中相同體積的值撇贺，獲取最大值艘狭。同時把體積大于w總容量的數(shù)據(jù)去掉巢音。
int main()
{
int n,w;
cin>>n>>w;
map<int,int > m;
int i,wi,vi;
for(i=0;i<n;i++)
{
cin>>wi>>vi;
if(wi<=w) // 費用大于w的去掉
{
if(m.find(wi)!=m.end())
{
if(m[wi]<vi) //費用(體積)相同時 選擇更大的價值
{
m[wi]=vi;
}
}
else
{
m[wi]=vi;
}
}
}
map<int,int>::iterator it;
it=m.begin();
while(it!=m.end())
{
cout<<it->first<<" "<<it->second<<endl;
it++;
}
return 0;
}
2.4 轉化為01 背包問題求解
01 背包問題是最基本的背包問題港谊，我們可以考慮把完全背包問題轉化為01 背包問題來解歧寺。
最簡單的想法是斜筐，考慮到第i 種物品最多選?V /Ci? 件顷链，于是可以把第i 種物品轉化為?V /Ci? 件費用及價值均不變的物品嗤练，然后求解這個01 背包問題煞抬。這樣的做法完全沒有改進時間復雜度革答，但這種方法也指明了將完全背包問題轉化為01 背包問題的思路：將一種物品拆成多件只能選0 件或1 件的01 背包中的物品残拐。更高效的轉化方法是：把第i 種物品拆成費用Ci * 2^k溪食、價值為Wi * 2^k 的若干件物品边败，其中k 取遍滿足Ci*2^k ≤ V 的非負整數(shù)。這是二進制的思想登疗。因為辐益，不管最優(yōu)策略選幾件第i 種物品智政，其件數(shù)寫成二進制后续捂，總可以表示成若干個2^k 件物品的和。這樣一來就把每種物品拆成O(log ?V /Ci?) 件物品矾克，是一個很大的改進胁附。
2.5 O(V N) 的算法
這個算法使用一維數(shù)組控妻，先看偽代碼：
你會發(fā)現(xiàn)，這個偽代碼與01 背包問題的偽代碼只有v 的循環(huán)次序不同而已洗做。
為什么這個算法就可行呢诚纸？首先想想為什么01 背包中要按照v 遞減的次序來循環(huán)畦徘。讓v 遞減是為了保證第i 次循環(huán)中的狀態(tài)F[i; v] 是由狀態(tài)F[i - 1, v - Ci] 遞推而來。換句話說溶握，這正是為了保證每件物品只選一次，保證在考慮“選入第i 件物品”這件策略時胀屿，依據(jù)的是一個絕無已經(jīng)選入第i 件物品的子結果F[i -1, v - Ci]包雀。而現(xiàn)在完全背包的特點恰是每種物品可選無限件宿崭，所以在考慮“加選一件第i 種物品”這種策略時，卻正需要一個可能已選入第i 種物品的子結果F[i, v-Ci]才写，所以就可以并且必須采用v遞增的順序循環(huán)葡兑。這就是這個簡單的程序為何成立的道理。
值得一提的是琅摩，上面的偽代碼中兩層for 循環(huán)的次序可以顛倒铁孵。這個結論有可能會帶來算法時間常數(shù)上的優(yōu)化。
這個算法也可以由另外的思路得出房资。例如蜕劝，將基本思路中求解F[i,v -Ci] 的狀態(tài)轉移方程顯式地寫出來岖沛，代入原方程中唉俗，會發(fā)現(xiàn)該方程可以等價地變形成這種形式：
C++代碼實現(xiàn)：
int main()
{
int n;
cin>>n;
while(n--)
{
int money;
cin>>money;
int i;
for(i=0;i<3;i++)
{
for(int j=0;j<=money;j++)
{
if(j>=v[i])
{
dp_1[j]=max(dp_1[j],dp_1[j-v[i]]+v[i]);
}
}
}
cout<<money-dp_1[money]<<endl;
}
return 0;
}
將這個方程用一維數(shù)組實現(xiàn)瘾境，便得到了上面的偽代碼。
最后抽象出處理一件完全背包類物品的過程偽代碼：
2.6 小結
完全背包問題也是一個相當基礎的背包問題，它有兩個狀態(tài)轉移方程聘殖。希望讀者能夠對這兩個狀態(tài)轉移方程都仔細地體會突照，不僅記住，也要弄明白它們是怎么得出來的游盲，最好能夠自己想一種得到這些方程的方法。
事實上熙卡，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來颓鲜，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。
3 多重背包問題
3.1 題目
有N 種物品和一個容量為V 的背包酌予。第i 種物品最多有Mi 件可用涎劈，每件耗費的空間是Ci扭吁，價值是Wi。求解將哪些物品裝入背包可使這些物品的耗費的空間總和不超過背包容量颁湖，且價值總和最大涎永。
3.2 基本算法
這題目和完全背包問題很類似〔┩叮基本的方程只需將完全背包問題的方程略微一改即可。因為對于第i 種物品有Mi + 1 種策略：取0 件尿瞭，取1 件……取Mi 件。令F[i, v]表示前i 種物品恰放入一個容量為v 的背包的最大價值幅聘，則有狀態(tài)轉移方程：
3.3 轉化為01 背包問題
另一種好想好寫的基本方法是轉化為01 背包求解：把第i 種物品換成Mi 件01背包中的物品燃箭，則得到了物品數(shù)為∑Mi 的01 背包問題。直接求解之舍败，復雜度仍然是O(V ∑Mi)招狸。
但是我們期望將它轉化為01 背包問題之后，能夠像完全背包一樣降低復雜度邻薯。
仍然考慮二進制的思想裙戏，我們考慮把第i 種物品換成若干件物品，使得原問題中第i 種物品可取的每種策略——取0...Mi 件——均能等價于取若干件代換以后的物品厕诡。另外累榜，取超過Mi 件的策略必不能出現(xiàn)。方法是：將第i 種物品分成若干件01 背包中的物品木人，其中每件物品有一個系數(shù)信柿。這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。令這些系數(shù)分別為1醒第、 2渔嚷、2^2 ... 2^k-1,Mi - 2^k + 1，且k 是滿足Mi - 2^k + 1 > 0 的最大整數(shù)稠曼。例如形病，如果Mi為13，則相應的k = 3，這種最多取13 件的物品應被分成系數(shù)分別為1漠吻、2量瓜、4、6 的四件
物品途乃。
分成的這幾件物品的系數(shù)和為Mi绍傲，表明不可能取多于Mi 件的第i 種物品。另外這種方法也能保證對于0 ...Mi 間的每一個整數(shù)耍共，均可以用若干個系數(shù)的和表示烫饼。這里算法正確性的證明可以分0... 2^(k-1) 和2k...Mi 兩段來分別討論得出，希望讀者自己思考嘗試一下试读。
這樣就將第i 種物品分成了O(logMi) 種物品杠纵， 將原問題轉化為了復雜度為O(V ∑logMi) 的01 背包問題，是很大的改進钩骇。
下面給出O(logM) 時間處理一件多重背包中物品的過程：
希望你仔細體會這個偽代碼比藻，如果不太理解的話，不妨翻譯成程序代碼以后倘屹，單步執(zhí)行幾次银亲，或者頭腦加紙筆模擬一下，以加深理解纽匙。
c++代碼實現(xiàn):
void completePack(int dp[],int value,int weight,int total)
{
int i;
for(i=weight;i<=total;i++)
{
dp[i]=max(dp[i],dp[i-weight]+value);
}
}
void ZeroOnePack(int dp[],int value,int weight,int total)
{
int i;
for(i=total;i>=weight;i--)
{
dp[i]=max(dp[i],dp[i-weight]+value);
}
}
//多重背包問題 優(yōu)化 一維數(shù)組 二進制的思想 時間復雜度為O(V*Σlog n[i])
void mutiPack(int dp[],int value,int weight,int amount,int total)
{
if(weight*amount>total)
{
completePack(dp,value,weight,total);
}
else
{
int k=1;
while(amount-k>=0)
{
ZeroOnePack(dp,k*value,k*weight,total);
amount-=k;
k*=2;
}
ZeroOnePack(dp,amount*value,amount*weight,total);
}
}
int main()
{
int n,w;
cin>>n>>w;
int i;
int wi,vi,ci;
for(i=0;i<n;i++)
{
cin>>wi>>vi>>ci;
mutiPack(dp_1,vi,wi,ci,w);
}
cout<<dp_1[w]<<endl;
return 0;
}
3.4 可行性問題O(V N) 的算法
當問題是“每種有若干件的物品能否填滿給定容量的背包”群凶，只須考慮填滿背包的可行性，不需考慮每件物品的價值時哄辣，多重背包問題同樣有O(V N) 復雜度的算法。
例如赠尾，可以使用單調(diào)隊列的數(shù)據(jù)結構力穗，優(yōu)化基本算法的狀態(tài)轉移方程，使每個狀態(tài)的值可以以均攤O(1) 的時間求解气嫁。
下面介紹一種實現(xiàn)較為簡單的O(V N) 復雜度解多重背包問題的算法当窗。它的基本思想是這樣的：設F[i; j] 表示“用了前i 種物品填滿容量為j 的背包后，最多還剩下幾個第i 種物品可用”寸宵，如果F[i, j] = -1 則說明這種狀態(tài)不可行崖面，若可行應滿足0 ≤ F[i,j] ≤ Mi。
遞推求F[i,j] 的偽代碼如下：
最終F[N][0 ... V ] 便是多重背包可行性問題的答案梯影。
3.5 小結
在這一講中巫员，我們看到了將一個算法的復雜度由O(V ∑Mi) 改進到O(V ∑ logMi) 的過程，還知道了存在復雜度為O(V N) 的算法甲棍。希望你特別注意“拆分物品”的思想和方法简识，自己證明一下它的正確性，并將完整的程序代碼寫出來。
