寫在前面

由于本人實(shí)力尚淺，接觸算法沒多久，寫這篇blog僅僅是想要提升自己對(duì)算法的理解，如果各位讀者發(fā)現(xiàn)什么錯(cuò)誤，懇請(qǐng)指正，希望和大家一起進(jìn)步。(●’?’●)

DP(動(dòng)態(tài)規(guī)劃）核心講解

狀態(tài)表示：用一個(gè)數(shù)組f[][](數(shù)組可能是一維也可能是二維，根據(jù)具體題目具體分析）來表示某個(gè)集合，這個(gè)集合表示所有的做法，集合存的值就是對(duì)應(yīng)做法的屬性（一般是max，min，count）（換句話說：f[i][j]表示在限制i,j下做法的屬性）
狀態(tài)轉(zhuǎn)移：本質(zhì)上是一個(gè)優(yōu)化的過程，就是不斷更新狀態(tài)。

01背包問題

題目

思路

重要變量說明:
f[][[]:用于狀態(tài)表示；
w[]：記錄每個(gè)物品的價(jià)值；
v][]：記錄每個(gè)物品的體積；

1. 定義二維數(shù)組f[][],其中f[i][j]表示在前i個(gè)物品，背包容積為j的限制下所能裝下的最大價(jià)值。這里的f[i][j]就是做法的集合，f[i][j]的值就是最大價(jià)值即屬性。
2. 從i=1開始枚舉，對(duì)于第i個(gè)物品，都有選和不選兩種選擇：
   • 如果不選第i個(gè)物品，那么狀態(tài)轉(zhuǎn)移方程為f[i][j]=f[i-1][j]
   • 如果選擇第i個(gè)物品，那么狀態(tài)轉(zhuǎn)移方程為f[i][j]=f[i-1][j-v[i]]+w[i]
3. 我們因?yàn)橐笞畲髢r(jià)值，所以對(duì)上面兩種情況去max即可

代碼（不優(yōu)化版，二維數(shù)組）

#include<iostream>

using namespace std;
const int N=1010;
int f[N][N],v[N],w[N];

int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)   
        cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)       //從第一個(gè)物品開始選，直到最后一個(gè)物品結(jié)束
        for(int j=1;j<=V;j++)       //從最小的體積開始，直到背包的最大的容積
        {
            if(j-v[i]>=0)       //可以裝第i個(gè)物品
                f[i][j]=f[i-1][j-v[i]]+w[i];        //狀態(tài)轉(zhuǎn)移
            f[i][j]=max(f[i][j],f[i-1][j]);     //狀態(tài)轉(zhuǎn)移，兩種情況取最大值
        }
    cout<<f[n][V]<<endl;
    return 0;
}

優(yōu)化1（滾動(dòng)數(shù)組）

注意： 這里優(yōu)化的的是空間而不是時(shí)間

思路

我們注意到其實(shí)上面寫的f[i][j]其實(shí)每次計(jì)算只是用到了第i層和第i-1層，所以我們數(shù)組的第一維其實(shí)只用開兩個(gè)即可。

代碼

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N];
int w[N];
int f[N][N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++) scanf("%d%d",&v[i],&w[i]);
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= m;j ++){
            f[i % 2][j] = f[(i - 1) % 2][j];
            if(j >= v[i]) f[i % 2][j] = max(f[i % 2][j],f[(i - 1) % 2][j - v[i]] + w[i]);
        }
    }
    printf("%d",f[n % 2][m]);
    return 0;
}

優(yōu)化2（一維數(shù)組）

我們可以把二維數(shù)組優(yōu)化到一維數(shù)組
為什么可以這樣變形呢？我們定義的狀態(tài)f[i][j]可以求得任意合法的i與j最優(yōu)解，但題目只需要求得最終狀態(tài)f[n][m]，因此我們只需要一維的空間來更新狀態(tài)

思路

1. 定義f[]表示狀態(tài)，f[j]表示在N個(gè)物品，背包容積為j下所能裝下的最大價(jià)值。
2. 也還是從i開始枚舉，表示選與不選第i個(gè)物品。

注意

我們要逆序枚舉背包容積，即每次循環(huán)從背包的最大容積開始枚舉。
**原因如下：**在二維情況下，狀態(tài)f[i][j]是由上一輪i - 1的狀態(tài)得來的，f[i][j]與f[i - 1][j]是獨(dú)立的。而優(yōu)化到一維后，如果我們還是正序，則有f[較小體積]更新到f[較大體積]，則有可能本應(yīng)該用第i-1輪的狀態(tài)卻用的是第i輪的狀態(tài)。
**簡(jiǎn)單來說：**簡(jiǎn)單來說，一維情況正序更新狀態(tài)f[j]需要用到前面計(jì)算的狀態(tài)已經(jīng)被「污染」，逆序則不會(huì)有這樣的問題。
相信即使我上面解釋的已經(jīng)夠詳細(xì)了，但是有些讀者沒有看明白，沒關(guān)系，我下面舉個(gè)栗子就非常清楚了。
栗子： 假設(shè)總共有三件物品，背包容積為10。

    如果 j 層循環(huán)是遞增的： 
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= m; j++) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

模擬過程如下

    當(dāng)還未進(jìn)入循環(huán)時(shí):
    f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
    f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;
    當(dāng)進(jìn)入循環(huán) i == 1 時(shí)：
    f[4] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;
    f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
    f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
    f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;
    重點(diǎn)來了！??！
    f[8] = max(f[8], f[4] + 5); 即max(0, 5 + 5) = 10; 即f[8] = 10;
    這里就已經(jīng)出錯(cuò)了
    因?yàn)榇藭r(shí)處于 i == 1 這一層，即物品只有一件，不存在單件物品滿足價(jià)值為10
    所以已經(jīng)出錯(cuò)了。

    如果 j 層循環(huán)是逆序的：
    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]);
        }
    }

模擬過程如下

    當(dāng)還未進(jìn)入循環(huán)時(shí):
    f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
    f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;
    當(dāng)進(jìn)入循環(huán) i == 1 時(shí)：w[i] = 5; v[i] = 4;
    j = 10：f[10] = max(f[10], f[6] + 5); 即max(0, 5) = 5; 即f[10] = 5;
    j = 9 ：f[9] = max(f[9], f[5] + 5); 即max(0, 5) = 5; 即f[9] = 5;
    j = 8 ：f[8] = max(f[8], f[4] + 5); 即max(0, 5) = 5; 即f[8] = 5;
    j = 7 ：f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;
    j = 6 ：f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
    j = 5 ：f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
    j = 4 ：f[6] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;
    當(dāng)進(jìn)入循環(huán) i == 2 時(shí)：w[i] = 6; v[i] = 5; 
    j = 10：f[10] = max(f[10], f[5] + 6); 即max(5, 11) = 11; 即f[10] = 11;
    j = 9 ：f[9] = max(f[9], f[4] + 6); 即max(5, 11) = 5; 即f[9] = 11;
    j = 8 ：f[8] = max(f[8], f[3] + 6); 即max(5, 6) = 6; 即f[8] = 6;
    j = 7 ：f[7] = max(f[7], f[2] + 6); 即max(5, 6) = 6; 即f[7] = 6;
    j = 6 ：f[6] = max(f[6], f[1] + 6); 即max(5, 6) = 6; 即f[6] = 6;
    j = 5 ：f[5] = max(f[5], f[0] + 6); 即max(5, 6) = 6; 即f[5] = 6;
    當(dāng)進(jìn)入循環(huán) i == 3 時(shí): w[i] = 7; v[i] = 6; 
    j = 10：f[10] = max(f[10], f[4] + 7); 即max(11, 12) = 12; 即f[10] = 12;
    j = 9 ：f[9] = max(f[9], f[3] + 6); 即max(11, 6) = 11; 即f[9] = 11;
    j = 8 ：f[8] = max(f[8], f[2] + 6); 即max(6, 6) = 6; 即f[8] = 6;
    j = 7 ：f[7] = max(f[7], f[1] + 6); 即max(6, 6) = 6; 即f[7] = 6;
    j = 6 ：f[6] = max(f[6], f[0] + 6); 即max(6, 6) = 6; 即f[6] = 6;

代碼（優(yōu)化后，一維數(shù)組）

#include<iostream>

using namespace std;
const int N=1010;
int f[N],v[N],w[N];

int main()
{
    int n,m;
    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--)        //逆序，防止被數(shù)據(jù)污染
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}

???總結(jié)
“種一顆樹最好的是十年前,其次就是現(xiàn)在”
所以,
“讓我們一起努力吧,去奔赴更高更遠(yuǎn)的山海”

如果有錯(cuò)誤?,歡迎指正喲??

??如果覺得收獲滿滿,可以動(dòng)動(dòng)小手,點(diǎn)點(diǎn)贊??,支持一下喲??文章來源地址http://www.zghlxwxcb.cn/news/detail-776837.html

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃——01背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！