什么是動態規劃？
動態規劃算法（dynamic programing），是一種由遞推為基礎的比貪心更穩定的一種優化策略，為運籌學的一部分。就是通過以遞推為基礎的手段非暴力求出最值。
它的總體思想其實就是一個比較過程：假如你有一個數據，它的價值是x，代價為y，如果用動態規劃就是和你不加這個元素和你加上這個元素的價值減去他的代價的二值做最值比較。
(資料圖片)
動態規劃的思想用的很多就比如：經濟上的盈虧、概率等。
今天有于時間關系，只講零一背包
1.01背包問題
零一背包是一種經典的有代價和價值兩個元素干涉的最值問題.
01背包是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2至Wn，與之相對應的價值為P1,P2至Pn。01背包是背包問題中最簡單的問題。01背包的約束條件是給定幾種物品，
每種物品有且只有一個，并且有權值和體積兩個屬性。在01背包問題中，因為每種物品只有一個，對于每個物品只需要考慮選與不選兩種情況。如果不選擇將其放入背包中，則不需要處理。如果選擇將其放入背包中，
由于不清楚之前放入的物品占據了多大的空間，需要枚舉將這個物品放入背包后可能占據背包空間的所有情況。
但在程序里需要一個二維數組來表達：
首先，什么是狀態？
狀態就是這個二維數組 f[i][j] 表示的什么意思，根據動態規劃的思想就可以推出結論：f[i][j]就是第i,j個位置上算出來的最優解
可是，問題來啦，咋求這個最優解呢？于是就必須用到我們的遞推試，叫做狀態轉移方程。
f[i][j]=max(f[i][j],f[i][j-w[i]]+c[i]);
其中w[i]是代價，c[i]是價值。
so,上代碼：
1 /* 2 這里就直接出滾動數組優化的代碼了 3 滾動數組就是把前面沒最優化的數據覆蓋 4 以達到節省空間的目的。 5 */ 6 #include7 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]);//滾動數組優化一維 19 }20 }21 cout << f[m];22 return 0;23 }
