1.?前置知識

動態(tài)規(guī)劃與圖論，前綴和與差分等有模板的算法不同，動態(tài)規(guī)劃更考察思維能力，而不是運用模板的能力。

個人認(rèn)為 Acwing?關(guān)于動態(tài)規(guī)劃的講解比較容易理解。我會根據(jù) Acwing?的動態(tài)規(guī)劃解題思路來講解題目。

雖說動態(tài)規(guī)劃沒有固定的模板，但是還是有相對固定的套路。但是思維能力以及經(jīng)驗積累在解決動態(tài)規(guī)劃的題目中十分重要。

集合：表示狀態(tài)中每一個下標(biāo)位置可能的選擇。

屬性：表示狀態(tài)中每一個下標(biāo)位置可能的選擇的屬性。(一般是最大值或者最小值，將選擇附加上屬性，就會得到每一個下標(biāo)位置的最終結(jié)果)。

狀態(tài)計算：將每一個狀態(tài)中的集合進行劃分，根據(jù)集合的劃分推出狀態(tài)轉(zhuǎn)移方程。

集合劃分的依據(jù)：劃分出來的所有集合的并集不得遺漏一個狀態(tài)中的任何選擇。但是可以重復(fù)。

這些東東可能會很抽象，后面的例題會幫助大家理解這寫東東。

2. 01背包問題 (來源：Acwing)

原題鏈接：2. 01背包問題 - AcWing題庫

題目描述：

有?N 件物品和一個容量是?V 的背包。每件物品只能使用一次。

第?i?件物品的體積是?vi，價值是?wi。

求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
輸出最大價值。

輸入格式：

第一行兩個整數(shù)，N，V，，用空格隔開，分別表示物品數(shù)量和背包容積。

接下來有?N?行，每行兩個整數(shù)?vi, wi，用空格隔開，分別表示第?i?件物品的體積和價值。

輸出格式：

輸出一個整數(shù)，表示最大價值。

數(shù)據(jù)范圍：

0 < N, V ≤1000
0< vi, wi ≤1000

輸入樣例：

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

我們直接按照上面給出的套路來：

狀態(tài)表示：f [i, j] (代表狀態(tài)是一個二維的，這里就不寫成二維數(shù)組的形式了，比較麻煩。)?

二維數(shù)組中每一個下標(biāo)代表的集合：從 1 -?i?個物品中選，并且總體積不超過?j?的選法的集合。

屬性：集合中選法的最大價值。(將屬性附加到集合得到的結(jié)果就是二維數(shù)組中每個下標(biāo)的結(jié)果)

狀態(tài)計算：

集合劃分：將狀態(tài)劃分成兩個集合：1：從1 -?i?個物品中選，選擇?i ，且價值不超過?j?的所有選法；2：從 1 - (i - 1)?個物品選，不選擇?i ，且價值不超過?j?的所有選法。

劃分依據(jù)的驗證：二維數(shù)組每一個下標(biāo)的最終值就是，代表從 1 -?i?個物品中選，且總體積不超過?j?的選法的價值最大值。顯然這個集合劃分沒有漏掉該下標(biāo)位置對應(yīng)的所有選法。

狀態(tài)轉(zhuǎn)移方程：根據(jù)集合劃分，我們只要求出劃分出的兩個集合中所有選法價值的最大值即可。

注意：j -?v[i]?必須保證?j >= v[i]?哦！最終的答案就是 f[N][V] 。

#include<iostream>
using namespace std;

const int N = 1010;
int v[N], w[N];
int f[N][N];
int m, n;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        cin >> v[i] >> w[i];
        
    f[0][0] = 0; // 全局變量默認(rèn)初始化為0，可以不寫
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[m][n] << endl;
        
    return 0;
}

?3.?空間優(yōu)化

直接將狀態(tài)從二維壓縮到一維，觀察結(jié)果會不會出錯：

f[ i ][ j ] = f[ i - 1][ j ]，用到的是上一層即?i - 1?層的狀態(tài)，若遍歷體積大小( j )是從小到大遍歷，那么狀態(tài)壓縮之后的計算結(jié)果就是用第 i?層的狀態(tài)來算的，不正確，因此我們需要改變遍歷的順序，從大到小遍歷。

f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])，用到的同樣是上一層的狀態(tài)，因此同樣不能從小到達(dá)遍歷體積，必須從大到小遍歷體積才能保證狀態(tài)的轉(zhuǎn)移是從上一層來的。

綜上所述，只需要改變體積的遍歷順序就可以將二維的狀態(tài)壓縮到一維。文章來源地址http://www.zghlxwxcb.cn/news/detail-529370.html

#include<iostream>
using namespace std;

const int N = 1010;
int v[N], w[N];
int f[N];
int m, n;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        cin >> v[i] >> w[i];
        
    f[0] = 0; // 全局變量默認(rèn)初始化為0，可以不寫
    for(int i = 1; i <= m; i++)
        for(int j = n; j - v[i] >= 0; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[n] << endl;
        
    return 0;
}

到了這里，關(guān)于動態(tài)規(guī)劃母題：01背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！