什么是動(dòng)態(tài)規(guī)劃？

動(dòng)態(tài)規(guī)劃算法（dynamic programing），是一種由遞推為基礎(chǔ)的比貪心更穩(wěn)定的一種優(yōu)化策略，為運(yùn)籌學(xué)的一部分。就是通過以遞推為基礎(chǔ)的手段非暴力求出最值。

它的總體思想其實(shí)就是一個(gè)比較過程：假如你有一個(gè)數(shù)據(jù)，它的價(jià)值是x，代價(jià)為y，如果用動(dòng)態(tài)規(guī)劃就是和你不加這個(gè)元素和你加上這個(gè)元素的價(jià)值減去他的代價(jià)的二值做最值比較。

(資料圖片)

動(dòng)態(tài)規(guī)劃的思想用的很多就比如：經(jīng)濟(jì)上的盈虧、概率等。

今天有于時(shí)間關(guān)系，只講零一背包

1.01背包問題

零一背包是一種經(jīng)典的有代價(jià)和價(jià)值兩個(gè)元素干涉的最值問題.

01背包是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2至Wn，與之相對(duì)應(yīng)的價(jià)值為P1,P2至Pn。01背包是背包問題中最簡單的問題。01背包的約束條件是給定幾種物品，

每種物品有且只有一個(gè)，并且有權(quán)值和體積兩個(gè)屬性。在01背包問題中，因?yàn)槊糠N物品只有一個(gè)，對(duì)于每個(gè)物品只需要考慮選與不選兩種情況。如果不選擇將其放入背包中，則不需要處理。如果選擇將其放入背包中，

由于不清楚之前放入的物品占據(jù)了多大的空間，需要枚舉將這個(gè)物品放入背包后可能占據(jù)背包空間的所有情況。

但在程序里需要一個(gè)二維數(shù)組來表達(dá)：

首先，什么是狀態(tài)？

狀態(tài)就是這個(gè)二維數(shù)組 f[i][j] 表示的什么意思，根據(jù)動(dòng)態(tài)規(guī)劃的思想就可以推出結(jié)論：f[i][j]就是第i,j個(gè)位置上算出來的最優(yōu)解

可是，問題來啦，咋求這個(gè)最優(yōu)解呢？于是就必須用到我們的遞推試，叫做狀態(tài)轉(zhuǎn)移方程。

f[i][j]=max(f[i][j],f[i][j-w[i]]+c[i]);

其中w[i]是代價(jià)，c[i]是價(jià)值。

so,上代碼：

1 /* 2 這里就直接出滾動(dòng)數(shù)組優(yōu)化的代碼了 3 滾動(dòng)數(shù)組就是把前面沒最優(yōu)化的數(shù)據(jù)覆蓋 4 以達(dá)到節(jié)省空間的目的。  5 */ 6 #include 7 using namespace std; 8 int f[105]; 9 int w[105],c[105];10 int main(){11     int n,m;12     cin >> n>>m;13     for(int i=1;i<=n;i++){14         cin >> w[i]>> c[i];15     }16     for(int i=1;i<=n;i++){17         for(int j=m;j>=w[i];j--){ 18             f[j]=max(f[j],f[j-w[i]]+c[i]);//滾動(dòng)數(shù)組優(yōu)化一維 19         }20     }21     cout << f[m];22     return 0;23 }