動(dòng)態(tài)規(guī)劃解題步驟:

動(dòng)態(tài)規(guī)劃問題，一般從三個(gè)步驟進(jìn)行考慮。

步驟一：集合及集合的狀態(tài)。

所謂的集合，就是一些方案的集合。

用 g[i][j] 表示從前 i 種物品中進(jìn)行選擇，且總體積不大于 j 的各個(gè)選法獲得的價(jià)值的集合。注意，g[i][j] 是個(gè)集合，表示一堆數(shù)：所有可能選出的價(jià)值。

例如 g[2][3] 從前 2 種物品中進(jìn)行選擇，且總體積不大于 3 的各個(gè)選法獲得的價(jià)值的集合。選擇方案有三種：都不選，價(jià)值為 0、選擇第 1 個(gè)物品，價(jià)值為 2、選擇第 2 個(gè)物品，價(jià)值為 4、選擇第 1，第 2 個(gè)物品，價(jià)值為 6。 g[2][3] = {0, 2, 4, 6}。

例如 g[3][4] 從前 3 種物品中進(jìn)行選擇，且總體積不大于 4 的各個(gè)選法獲得的價(jià)值的集合，選擇方案有三種：都不選，價(jià)值為 0、選擇第 1 個(gè)物品，價(jià)值為 2、選擇第 2 個(gè)物品，價(jià)值為 4、選擇第 3 個(gè)物品，價(jià)值為 4，選擇第 1，第 2 個(gè)物品，價(jià)值為 6，選擇第 1，第 3 個(gè)物品，價(jià)值為 6。 g[3][4] = {0, 2, 4, 4, 6, 6}。

i j 取不同的值，對(duì)應(yīng)不同的 g[i][j]，也就是對(duì)應(yīng)不同的集合。

用 f[i][j] 表示從前 i 種物品中進(jìn)行選擇，總體積小于等于 j 所能獲得的最大價(jià)值, 注意，f[i][j] 是個(gè)一個(gè)數(shù)，是g[i][j] 這個(gè)集合中的最大值。很明顯，f[i][j] 就是 g[i][j] 中的最大值。i j 取不同的值，就對(duì)應(yīng)不同的 f[i][j]，即對(duì)應(yīng)不同的集合的最大值。

例如 f[2][3] 表示從前 2 種物品中進(jìn)行選擇，且總體積不大于 3 的獲得的最大價(jià)值。f[2][3] = max(g[2][3]) = 6。

例如 f[3][4] 表示從前 3 種物品中進(jìn)行選擇，且總體積不大于 4 的獲得的最大價(jià)值。f[3][4] = max(g[3][4]) = 6。

g[i][j] 的最大值就是 f[i][j]。

如果我們能把所有集合對(duì)應(yīng)的最大值都求出來，即求出了 f[0][0] ~ f[N][V]， f[N][V] 的含義是在前 N 種物品中進(jìn)行選擇，總體積不大于 V 所獲得的最大價(jià)值，就是我們要找的答案。

注意，我們不需要把各個(gè)集合的所有元素都找出來，只需要求出各個(gè)集合的最大值就能找到答案。下面就是如何求出各個(gè)集合的最大值。

步驟二：狀態(tài)計(jì)算（求某個(gè)集合的最大值）。

g[i][j] 是從前 i 個(gè)物品中進(jìn)行選擇，且總體積不大于 j 的各個(gè)選法獲得的價(jià)值的集合。

f[i][j] 是從前 i 種物品中進(jìn)行選擇，總體積小于等于 j 所能獲得的最大價(jià)值。

f[i][j] 是集合 g[i][j] 的最大值。

所謂的狀態(tài)計(jì)算是指，如何將 f[i][j] 算出來。

如果把各個(gè)集合 g[i][j] 的狀態(tài) f[i][j] 求出來， f[N][V] 就是要找的答案。

對(duì)于上面的例題，g[2][3] 表示從前 2 種物品中選擇，總體積小于等于 3 的所有選擇方案獲得的價(jià)值的集合。

選擇方案有 三 種：方案1. 只選物品1，價(jià)值為 2。 方案2. 只選物品 2，價(jià)值為 4。方案3. 同時(shí)選物品 1 和物品 2，價(jià)值為 6。

g[i][j] = {2， 4， 6}。f[i][j] 為該集合中的最大值 6。

為了求出f[i][j]，我們可以使用下面的方法。

將 g[i][j] 這個(gè)集合劃分成互斥的 A B 兩部分。

A 部分是選法中不包含第 i 件物品。B 部分是選法中包含第 i 件物品。只要將 A 部分的最大值和 B 部分的最大值求出來，兩者中較大的值就是 g[i][j] 的最大值，也就是 f[i][j]。。

A 部分，等價(jià)于從前 i - 1 件物品中選擇，選出的物品總體積小于等于 j 的所有方案獲得的價(jià)值集合，也就是 g[i - 1][j]。g[i - 1][j]這個(gè)集合中的最大值是 f[i - 1][j]，所以 A 部分的最大值就是 f[i - 1][j]。

B 部分等價(jià)于從前 i 件物品中選擇，并且必須選擇第 i 件物品，且選出的物品總體積小于等于 j 的所有方案獲得的價(jià)值集合。

B 部分怎么求呢？直接求不太好求，可以試試曲線救國(guó)：

因?yàn)?B 部分對(duì)應(yīng)的方案中一定要選擇第 i 件物品。這時(shí)候有兩種情況。

給定的容量能放下第 i 件物品，那么第 i 件物品會(huì)占據(jù) vivi 的背包空間，剩下的背包空間為 j - vivi ?？梢岳^續(xù)從前 i - 1 種物品中，選出的物總體積小于等 j - vivi的物品放入背包中。

從前 i - 1 種物品中進(jìn)行選擇，選出的物總體積小于等 j - vivi 的方案獲得的價(jià)值集合為 g[i - 1][j - vivi] 。所以 B 部分的元素為 g[i-1][j - vivi] 中各個(gè)元素的值加上 wiwi 。g[i-1][j - vivi] 中的最大值為 f[i-1][j - vivi]， 因此 B 部分的最大值為 f[i-1][j - vivi] + wiwi 。

給定的容量不能能放下第 i 件物品，這時(shí)候背包里就不能放入第 i 件物品，因此 B 部分就是空集。B 部分的最大值為 0。

例如 g[2][3] 可以劃分成兩部分，A 部分是不包含第 2 種物品，對(duì)應(yīng)方案1。B部分是包含第 2 種物品，對(duì)應(yīng)方案 2 和方案 3。

A 部分的最大值是 f[2 - 1][3] = f[1][3] = 2。

B 部分的最大值是 f[2 - 1][3 - 2] + w2w2 = f[1][1] + 4 = 6。

所以集合g[2][3] 的最大值 f[2][3] = max(A，B) = max(2, 6) = 6。

通過上面分析，我們可以知道，g[i][j] 可以分成兩部分，A 部分是不包含第 i 種物品對(duì)應(yīng)所有選法獲的價(jià)值的集合，最大值是 f[i - 1][j]。B 部分是包含第 i 種物品對(duì)應(yīng)所有選法獲的價(jià)值的集合，最大值是 f[i-1][j - vivi] + wiwi 或 0。所以 g[i][j] 的最大值就是在 A 部分的最大值與 B 部分的最大值取個(gè)max，也就是:

從計(jì)算公式可以看出，f[i][j] 是由 f[i - 1][j -vivi ] 和 wiwi 計(jì)算出來的。也就是f[i][j]的值是可以從前面已經(jīng)計(jì)算出的 f 值求出來。如果我們能確定 f[i][j] 的一部分初始值，就能通過該公式，一步步計(jì)算得出 f[N][V]，也就是我們要找的答案。

步驟三：確定初始值

0 1 背包問題的有些狀態(tài)是能夠直接確定的。

例如 f[0][0]。

f[0][0] 的含義是從前 0 件物品中選擇，并且選出的物品總體積小于等于0 時(shí)所能得到的最大價(jià)值。總體積小于等于 0，說明一種物品都不能選擇，因此 f[0][0] = 0。同理 f[1][0] = 0，f[2][0] = 0 ··· f[N][0] = 0。

有了這些初始值，通過 i 從 1 遍歷 N，j 從 1 遍歷 V，就能一步步求出所有的 f[i][j] 了。

例如求 f[1][1]。f[1][1] = max(A, B) = max{f[0][1]，f[0][0] + 2} = max(0，2) = 2。

求 f[1][2]。f[1][2] = max(A, B) = max{f[0][2]，f[0][0] + 2} = max(0，2) = 2。

最后 f[N][V] 就是要找的答案。

這時(shí)候就可以寫代碼了：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m;
int v[N], w[N];//v 保存體積，w 保存價(jià)值
int f[N][N];//保存所有集合最值狀態(tài)int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ )cin >> v[i] >> w[i];for(int i = 0; i <= m; i++)//初始化，前 0 中物品中選擇{f[0][i] = 0;}for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= m; j ++){if(v[i] <= j)//能放入第 i 件物品的情況下，求f[i][j]f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);else//不能放入第 i 件物品的情況下，求f[i][j]f[i][j] = f[i - 1][j];}}cout << f[n][m] << endl;//f[n][m] 就是答案return 0;
}

優(yōu)化 動(dòng)態(tài)規(guī)劃的優(yōu)化一般都是對(duì)代碼或者集合最值方程進(jìn)行一個(gè)等價(jià)變形。在考慮動(dòng)態(tài)規(guī)劃問題的時(shí)候，一定要先把基本的形式寫出來，然后再對(duì)它進(jìn)行優(yōu)化。

首先，根據(jù)優(yōu)化前的起碼，f[i][j] 是從上到下，一行一行這樣填滿的：

看一下 f[i][j] 的計(jì)算公式：f[i][j] = max(A, B)。

只用到了f[i - 1][j]，f[i-1][j - vivi] ，即只用到了 f[i - 1] 這一層，并且用到的體積為 j 和 j - vivi ，都是小于等于 j 的。

因此可以從體積為 V 開始，利用f[i - 1]的數(shù)據(jù)，求解出 f[i][j]，把 f[i][j] 放到 f[i -1][j] 的位置上。這樣 f 數(shù)組就能優(yōu)化到一維了。

并且，當(dāng) 背包容量小于 vjvj 的時(shí)候，f[i][j] = max{f[i - 1][j]，0} = f[i - 1][j]。所以 j 只需要從 V 遍歷到 vjvj 即可。

寫下代碼：

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N];int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];for (int i = 1; i <= n; i ++ )for (int j = m; j >= v[i]; j -- )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}