背包九講學習ing

正在學習dp，持續更新背包九講，記錄每次學習的内容，希望對于你也有幫助。

若有錯誤，歡迎指正！！！

如果對于我所講解的問題有不懂的或者模糊的，歡迎在評論區評論，我定會在部落格中更新講解。

一、01背包

這是最基礎的一類背包問題:

有n件物品，容量為m的背包，每一件物品都有自己的容量c【i】和價值w【i】，問你能裝下最大的價值之和？

對于初學者來說，dp算法還是較難了解的，什麼是狀态轉移方程，他又怎麼能夠確定一定最優解呢？

我就01背包來說說我的看法（先不考慮空間優化）：

對于這道題目來說，

狀态轉移方程就是：dp【i】【j】=max（dp【i-1】【j】，dp【i-1】【j-c【i】】+w【i】）。

對于這個方程來說，

首先，dp數組表示背包容量為j時，考慮過前i個物品後，我的背包裡能裝下的最大價值。

其次，max裡的兩個參數分别含義是：1.我不拿第i件物品，那麼我的此時能裝下的最大價值之和就是前i-1個物品中最大價值之和。2.若是我拿了第i件物品，那麼我此時能裝下的最大價值之和就是前i-1個物品裝在j-c【i】的空間下的最大價值之和加上第i件物品的價值w【i】。

拿不拿這個決策取決于max裡兩個參數的大小。

最終，既然你是要輸出最大的價值之和，那麼當然要等到周遊完所有物品和容量才行，即輸出dp【n】【m】。

那麼這個狀态轉移方程應該怎麼用呢？

為了解決第二個問題（保證目前狀态下的最優解），我們必須要周遊完所有的物品和盡量使用完所有的容量。就需要周遊。

for(int i=1;i<=n;i++)//周遊所有的物品
        for(int j=1;j<=v;j++)//對于每一個物品所有容量情況下的最大價值之和
        {
            if(j-c[i]<0){dp[i][j]=dp[i-1][j];continue;}//防止數組越界
            dp[i][j]=maxi(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
        }
           

由代碼我們可以看到要加上一個判斷條件，就是防止數組越界。因為如果我目前的容量小于物品所需容量，那麼是肯定拿不了的，是以我們可以直接讓他等于前i-1個物品在目前容量上的最大價值之和。

附上完整代碼:

#include <iostream>
#include <cstring>
using namespace std;
int v,n;//0<=n<=10000;0<v<10000
int c[10005],w[10005];
int dp[10005][10005];
int maxi(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    while(cin>>n>>v)
    {
        if(v==0&&n==0)break;
        memset(c,0,sizeof(c));
        memset(w,0,sizeof(w));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            cin>>c[i]>>w[i];
        }
        for(int i=1;i<=n;i++)
            for(int j=0;j<=v;j++)
            {
                if(j-c[i]<0){dp[i][j]=dp[i-1][j];continue;}
                dp[i][j]=maxi(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
            }
        /*可供于測試dp的整個過程
        for(int i=1;i<=n;i++)
            {for(int j=0;j<=v;j++)
                cout<<dp[i][j]<<" ";
                cout<<endl;
            }
         */
        cout <<dp[n][v]<< endl;
    }
    return 0;
}
           

接下來說一下關于空間優化的問題。

我們知道上面代碼的時間複雜度和空間複雜度都是O（n*m）。由于肯定要周遊所有的i和j，是以若是不改變算法的話時間複雜度是肯定不會降低的，我們所能優化的也就隻有空間複雜度了。

那麼為什麼能優化空間複雜度，并且怎麼優化呢?

我們不難發現i在這裡隻是起着周遊所有物品的作用，不像j還會向前j-c【i】延伸，也就是一旦這個i便利過了我隻有在i+1的時候才會用到其他時間都不會用到，是以i的用處并不大，可以優化掉，這樣空間複雜度就降到了O（m）了。

那麼應該怎麼優化呢？（将dp【i】【j】變成dp【j】）

我們知道如果j小于c【i】則dp【i】【j】=dp【i-1】【j】，是以對于j小于c【i】我們不需要考慮，dp【j】不管就不會變化，達到同樣的效果。而為了使用dp【i-1】【j-c【i】】我們可以從後向前周遊j（由m到c【i】），這樣前i-1件物品的dp【j】就不會發生變化，相當于以前的dp【i-1】【j-c【i】】。

優化後的狀态轉移方程:dp【j】=max（dp【j】，dp【j-c【i】】+w【i】）;

注：還可以稍稍減少空間占用的地方就是c【i】和w【i】了，因為我們不需要儲存c和w這兩個數組，我們每一次隻用到了c【i】和w【i】，用完就不用了是以可以每次輸入時就進行dp，就可以省兩個數組的空間了。

附上優化空間後的代碼：

#include <iostream>
#include <cstring>
using namespace std;
int n,m,c,w,dp[12885];

int main()
{
    while(cin>>n>>m)
    {
    memset(dp,0,sizeof(dp));//初始化為0
    for(int i=1;i<=n;i++)
    {
        cin>>c>>w;
        for(int j=m;j>=c;j--)
        {
            if(dp[j]<(dp[j-c]+w))
            dp[j]=dp[j-c]+w;
        }
    }
    /*測試過程
    for(int i=0;i<=m;i++)cout<<dp[i]<<" ";
    cout<<endl;
    */
    cout<<dp[m]<<endl;
    }
    return 0;
}

           

二、完全背包

這個是在01背包的基礎上變形的一類背包問題：

同樣是有一個容量為m的背包，每一種物品的費用是c【i】，價值為w【i】，不同的是每一種物品不再隻是一件，而是有無窮多件，問能裝下大的最大價值？

既然都已經說了是在01背包的基礎上變形的，那麼他和01背包的解法肯定也具有一定的相似性。與01背包唯一不同的就是同一件物品可以選用多次。

先說一下這道題目的狀态轉移方程：dp【j】=max（dp【j】，dp【j-c【i】】+w【i】）;

你若仔細觀察，你會發現他和01背包的狀态轉移方程差不多。那麼大家心裡就會有疑問了，為什麼不同的問題會有相同的狀态轉移方程？（好奇心馬上就蹦了出來）

答案就是雖然兩者狀态轉移方程相同，但對于他的處理方式卻不同。01背包的周遊方式是i（0-n），j（m-c【i】）；而完全背包的j則是從c【i】到m。正是這小小一點的不同，就處理了兩個不同的問題。

下面我來解釋一下為什麼換一下周遊順序結果就會不一樣：

首先，在01背包上我們将j由m到c【i】（暫稱逆循環）的循環目的是為了利用i-1的dp【j-c【i】】，是以不能改變之前j之前的數組。

那麼完全背包為什麼又要正着循環呢，因為每一個物品我們都能夠選擇無限次，而且我們不再需要看他的上一件物品的dp【j-c【i】】。為了更好的了解，我先來模拟一下過程解釋一下為什麼能正循環。

對于每一個物品i，我們都要對其從c【i】循環到m，此時的dp【j】依舊是在與是否那這一件物品之間進行比較，若拿則是dp【j-c【i】】+w【i】，不拿則不變。是以說如果這個物品很好，我選擇拿了，那麼j從c【i】到m我就可能會拿多次這件物品，也就是對于這個物品i來說，在所有的容量j中都已經達到了最優的選擇，那麼我在下一件物品i+1時就不會再次考慮第i件物品了。之後繼續在下一次循環中找到每一種容量下我是否要拿第i+1件物品了。

總而言之，就是每一次循環完j後，對于第i件物品我都已經做出了最優的選擇。

剛才解釋了為什麼不需要考慮前i-1件物品了，接着說為什麼要正循環？

對于第i件物品，我先假設他就是最好的物品，我全部裝他會收獲最大價值，那麼你就要在dp【c【i】*{1~（m/c【i】）}】------ //注解：（m/c【i】）是我這個背包能裝下第i件物品的數量//-------- 的時候都要選擇這件物品，而你每一次判斷都是在dp【j】與dp【j-c【i】】之間進行比較，是以說我需要将前面我已經選擇了這件物品之後的dp數組更新再判斷，是以需要正循環j。

//開始寫了更多的注解，結果發現國文不好描述不清，想要更好的了解，就拿張紙，在紙上模拟一次j的循環，自然會了解。

注意：這道題和01背包一樣可以省略掉c【】，w【】數組的空間，雖然并無大礙，但能省即省吧！

附上完全背包代碼：

#include <iostream>
#include <cstring>
using namespace std;
int n,m,c,w;
int dp[10005];
int main()
{
    while(cin>>n>>m)
    {
        memset(dp,0,sizeof(dp));//初始化為0
        for(int i=0;i<n;i++)
        {
            cin>>c>>w;
            for(int j=c;j<=m;j++)
            {
                if(dp[j]<dp[j-c]+w)
                    dp[j]=dp[j-c]+w;
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}

           

對于前兩道題目的感觸：不要死記硬背，要多去了解，了解一下計算機的處理方式，多創新多鑽研！！！

國文功底不好，不敢多語，若有講解不清，可評論留言。

三、多重背包

問題：

與前兩道題類似，給你一個容量為m的背包，有n種物品，每一個的占用容量為c【i】，價值為w【i】，但是這種物品一共有num【i】件。與前兩道題不同的就在于他的數量可能不止一個，但也不是無窮個。

當我第一次看到這個題目時，我覺得難度突然上了一個檔次，覺得對于每一種物品都要考慮他的個數，不能按照統一思想去解決，就覺得很難。但當你靜下心仔細想想之後發現，其實很簡單，甚至都不用編寫新函數。

是不是有點驚訝？明明比前兩道題目複雜怎麼還說簡單了，其實這就考驗了你對于前兩種背包的了解了。

01背包：隻對于一件物品進行選擇。完全背包：對相同的物品選擇x件。（x在0~+00）

多重背包：對相同的物品選擇x件。（x在0~num）；是不是發現了其中的相似處。

下面說一下解法：

我們可以将多重背包分解成為01背包和完全背包；可以分解成01背包是毋庸置疑的（因為可以想象成更多件相同的物品罷了），那麼怎樣才能分解為完全背包呢？想一想如果這件物品的總重量之和大于背包容量m，那麼對于背包來說是不是和無窮件物品一樣，此時就可以把它當作完全背包來處理。你這樣寫出代碼後會發現出現TLE的問題，是因為你轉化為01背包的時間複雜度為O（n∑（num【i】）），是以你要優化，我們可以将num件物品分别分成1、2、4、8、…2的k次幂件物品作為單獨的一件物品處理。這樣你的代碼時間複雜度就降到了O（n∑log（num【i】））。

總結一下思想：

這道題主要是考驗對于前兩種背包的了解和熟練應用。還有就是對于01背包問題的優化處理，把num分解成不同2k次幂件物品，大大降低了時間複雜度。

注：這道題使用的依舊是一維的dp數組，依舊不需要設定c【i】，w【i】，num【i】三個數組，可以減少一點空間占用。

附上最終代碼：

#include <iostream>
#include <cstring>
using namespace std;
int c,w,num,n,m,dp[10005];
int maxi(int a,int b)
{
    return a>b?a:b;
}
void onepack(int c,int w)//01背包
{
    for(int i=m;i>=c;i--)
        dp[i]=maxi(dp[i],dp[i-c]+w);
}
void compack(int c,int w)//完全背包
{
    for(int i=c;i<=m;i++)
        dp[i]=maxi(dp[i],dp[i-c]+w);
}
int main()
{
    while(cin>>n>>m)
    {
        memset(dp,0,sizeof(dp));//初始化為0
        for(int i=0;i<n;i++)
        {
            cin>>c>>w>>num;
            if(num*c>m)//若num件物品總占容量超過m，背包裝不下則相當于無窮件i件物品，等同于完全背包
                compack(c,w);
            else//反之，若小于m，将num件物品分成很多個不同容量的物品則相當于01背包
            {
                int k=1;
                while(k<num)
                {
                    onepack(k*c,k*w);
                    num-=k;
                    k*=2;//k=1、2、4、8...
                }
                onepack(num*c,num*w);//剩下的所有再次當作一個01背包處理
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}

           

四、混合三種背包

問題：

同樣是n種物品，容量為m的背包，每一個有自己的占容量c【i】和價值w【i】，但是每一件可能隻能拿一件也可能無限件，也可能有上限。

相信看過前三種背包問題的人都有感觸，這道題目和多重背包很像，就是由三種背包混合在一起。其實就是一個判斷，具體的不多講，詳細的全部在前三個背包講解裡面。

直接附上代碼吧：

#include <iostream>
#include <cstring>
using namespace std;
int c,w,num,n,m,dp[10005];
int maxi(int a,int b)
{
    return a>b?a:b;
}
void onepack(int c,int w)//01背包
{
    for(int i=m;i>=c;i--)
        dp[i]=maxi(dp[i],dp[i-c]+w);
}
void compack(int c,int w)//完全背包
{
    for(int i=c;i<=m;i++)
        dp[i]=maxi(dp[i],dp[i-c]+w);
}
void mulpack(int c,int w,int num)
{
    if(num*c>m)//若num件物品總占容量超過m，背包裝不下則相當于無窮件i件物品，等同于完全背包
                compack(c,w);
    else//反之，若小于m，将num件物品分成很多個不同容量的物品則相當于01背包
    {
        int k=1;
        while(k<num)
        {
            onepack(k*c,k*w);
            num-=k;
            k*=2;//k=1、2、4、8...
        }
        onepack(num*c,num*w);//剩下的所有再次當作一個01背包處理
    }
}
int main()
{
    while(cin>>n>>m)
    {
        memset(dp,0,sizeof(dp));//初始化為0
        for(int i=0;i<n;i++)
        {
            cin>>c>>w>>num;//由于沒有具體題目，是以令num=-1為無窮件
            if(num==1)
                onepack(c,w);
            else if(num==-1)
                compack(c,w);
            else
                mulpack(c,w,num);
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}

           

五、二維背包問題

問題：依舊是n種物品，不同的是你有一個容量為m的背包和p的錢，每一件物品有自己的所占容量c【i】和價格d【i】以及自己的價值w【i】。

看到這裡，大家都會發現背包問題都是一級一級的往上加的。

接下來說說我對于這道題目的了解：

這道題目，其實就是相當于多了一個因素要考慮，就是他的價格。因為容量和價格之間沒有互相影響的因素，是以我們可以把它分開考慮。這裡的分開考慮隻是想說價格與容量之間沒有聯系，隻需在将dp數組上加一維。狀态轉移方程是：dp【j】【k】=max（dp【j】【k】，dp【j-c【i】】【k-d【i】】+w【i】）

了解之後發現處理方式就是和01背包和完全背包一樣。

隻不過需要多一層循環k，這裡當然也是為了周遊完所有的j和k。

最後附上代碼：

/*
代碼沒有實際測試資料，是以最終是否能ac尚不可知，但思想肯定就是這樣的。
*/
#include <iostream>
#include <cstring>
using namespace std;
int c,d,w,num,n,m,p,dp[10005][10005];
int maxi(int a,int b)
{
    return a>b?a:b;
}
void onepack(int c,int d,int w)//01背包
{
    for(int i=m;i>=c;i--)
        for(int j=p;j>=d;j--)
        dp[i][j]=maxi(dp[i][j],dp[i-c][j-d]+w);
}
void compack(int c,int d,int w)//完全背包
{
    for(int i=c;i<=m;i++)
        for(int j=d;j<m;j++)
        dp[i][j]=maxi(dp[i][j],dp[i-c][j-d]+w);
}
void mulpack(int c,int d,int w,int num)
{
    if(num*c>m||num*d>p)//若num件物品總占容量超過m，或者nun件物品錢數大于你帶的錢，背包裝不下則相當于無窮件i件物品，等同于完全背包
                compack(c,d,w);
    else//反之，若小于m，将num件物品分成很多個不同容量的物品則相當于01背包
    {
        int k=1;
        while(k<num)
        {
            onepack(k*c,k*d,k*w);
            num-=k;
            k*=2;//k=1、2、4、8...
        }
        onepack(num*c,num*d,num*w);//剩下的所有再次當作一個01背包處理
    }
}
int main()
{
    while(cin>>n>>m>>p)
    {
        memset(dp,0,sizeof(dp));//初始化為0
        for(int i=0;i<n;i++)
        {
            cin>>c>>d>>w>>num;//由于沒有具體題目，是以令num=-1為無窮件
            if(num==1)
                onepack(c,d,w);
            else if(num==-1)
                compack(c,d,w);
            else
                mulpack(c,d,w,num);
        }
        cout<<dp[m][p]<<endl;
    }
    return 0;
}

           

其實在更高維的問題中也是一樣的邏輯，隻要各種因素之間沒有關系，你就可以通過增加維數來解決問題。

若有錯誤，歡迎指正！

----持續更新，喜愛可關注哦------