算法介紹
動态規劃：
動态規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動态規劃算法與分治法類似，其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的（自底向上求解，底層的解可作為上層解的基礎 ）。
問題執行個體
問題描述：
題目：
給定N個物品,每個物品有一個重量W和一個價值V.你有一個能裝M重量的背包.問怎麼裝使得所裝價值最大.每個物品隻有一個.
輸入格式：
輸入的第一行包含兩個整數n, m，分别表示物品的個數和背包能裝重量。
以後N行每行兩個數Wi和Vi,表示物品的重量和價值
輸出格式：
輸出1行，包含一個整數，表示最大價值。輸出1行，包含一個整數，表示最大價值。
樣例輸入：
3 5
2 3
3 5
4 7
樣例輸出：
8
資料規模和約定
1<=N<=200,M<=5000.
問題分析
我們最終需要解決的問題是背包極限重量為m時，從n個物品中選出價值最大的組合。我們可以使用動态規劃的思想，将n個物品，m重量劃分為1 ~ n，1 ~ m 的小型背包，直到達到n，m。
僞代碼：
①設一個數組dp [][] ，dp [i][j] 代表當選完前i個物品，此時極限重量為j時的最大價值，初始都設為0，每次輸入的物品重量和價值分别用 w 和 v 表示。
②利用動态規劃的思想，i 從1 ~ n，j 從1 ~ m，雙重嵌套循環。
③對此時的 j 進行判斷，如果此時的 j < w ，說明放不下該物品，即 dp [i][j] = dp [i-1][j]（未放該物品，傳回容量相同的上一物品）；如果此時的 j >= w ，說明該物品可以放下，但需要判斷此時放該物品是否價值最大，即 dp[i][j] = max( dp[i-1][j], dp[i-1][j-w] + v) （一種情況是不放，前一個物品達到次重量時的最大價值；另一種情況是放，則需要減去該物品的重量并退回上一物品，再加上價值。前一個物品到達未放該物品的重量時最大價值加上該物品的價值）
④直到 i = n，j = m，結束，dp [n][m] 即為所求解。
dp[][]如下圖：
代碼：
#include <iostream>
using namespace std;
int dp[201][5001]={0};//dp[n][m]數組代表前n個物品選擇放到容量為m的背包中的最大價值
int main() {
int n, m;
cin >> n >> m; //輸入物體數量和最大重量
for(int i = 1; i <= n; i++) {
int w, v;
cin >> w >> v;// 輸入目前物體的重量和價值
for(int j = 1; j <= m; j++) {
//當目前物體的重量小于此時背包剩餘容量時，考慮是否放入該物體
if (j >= w)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
//當目前物體的重量大于背包剩餘容量時，無法放入
else
dp[i][j] = dp[i-1][j];
}
}
cout << dp[n][m];
return 0;
}
結果：
解決該問題的關鍵是将 n，m 從1開始逐一劃分，然後用 dp[][] 來記錄此時的最大價值，動态規劃的特點就是原先計算的最優值已經記錄，可以直接用，dp [i-1][j-w] + v 中的（j - w）即是此時的背包把将要放入的物品先拿出，觀察此時剩餘部分的最大價值，再加上此物品的價值，此時為放入該物品後的最大價值。
記錄整理一些學習中的問題，如果有不恰當和錯誤的地方，歡迎批評指正~