一、01背包問題

問題描述：

有 N 件物品和一個容量為 V 的背包，每件物品有各自的價值且只能被選擇一次，要求在有限的背包容量下，裝入的物品總價值最大。

樸素01背包

1. 狀態(tài)f[i , j]定義：在前i個物品中選，總體積不超過j的價值最大值
2. 狀態(tài)轉(zhuǎn)移
   1）選第i個物品：f[i,j] = f[i-1,j]
   2）不選第i個物品：f[i,j] = f[i-1, j-v[i] ] +w[i]
   我們的決策是如何取到最大價值，因此以上兩種情況取max( )

for(int i = 1; i <= n; i++) 
        for(int j = 0; j <= m; j++)
        {
            //  當前背包容量裝不進第i個物品，則價值等于前i-1個物品
                f[i][j] = f[i - 1][j];
            // 能裝，需進行決策是否選擇第i個物品
            if(j>=v[i])    
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }           

01背包優(yōu)化成一維

一維01背包就是將狀態(tài)f[i,j] 優(yōu)化到一維f[j] ，減低了內(nèi)存的開銷，使代碼更簡潔。

這種方法適合任何背包問題，在接下來的所有背包問題我們都是用一維的方法來分析。

1. 為什么可以這樣變形呢？

? 從樸素01背包問題來看，我們最終想要的答案是f[n,m] ,跟前n-1層無關(guān)，只是在計算的時候才會用到，但是用到的并不是所有的數(shù)據(jù)，我們通過狀態(tài)轉(zhuǎn)移可以發(fā)現(xiàn)我們當前層的轉(zhuǎn)移只用到了上一層的數(shù)據(jù)，因此我們只需要保存上一層的數(shù)據(jù)，每次用上一層的數(shù)據(jù)計算即可。

2. 在二維變?yōu)橐痪S的時候，有什么需要注意？

1） 在枚舉背包容量的時候需要逆序

? 因為在計算的我們是用較小的體積去更新較大的體積，所有我們每次在更新的時候，用到的是本層的狀態(tài)，而不是上一層的狀態(tài)。

2） 如何由二維優(yōu)化到一維

我們只需要將前面一維刪掉即可，具體變化如下：

      for(int i = 1; i <= n; i++) 
              for(int j = 1; j <= m; j++)
              {
                  //  當前背包容量裝不進第i個物品，則價值等于前i-1個物品
                      f[i][j] = f[i - 1][j];  	//優(yōu)化前
                      f[j] = f[j]      			//優(yōu)化后
           
                  // 能裝，需進行決策是否選擇第i個物品
                  if(j>=v[i])    
                      f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);  //優(yōu)化前
                      f[j] = max(f[j],f[j - v[i]]+w[i]);					//優(yōu)化后
              }    

接下來我們調(diào)整上述代碼中出現(xiàn)的一些冗余代碼，具體如下

• 由于f[j] = f[j] 是恒等式，無意義，所有我們?nèi)サ簟?/p>

• 我們將if(j>=v[i])放到循環(huán)條件里面。

這步為什么成立？變成一維之后，在j<v[i]的時候，由于我們用到的數(shù)據(jù)就是上一層的數(shù)據(jù)，所以我們不需要改變當前f的值。只有當j>=v[i]的時候，我們才拿上一層的值和放當前物品的價值取max即可。

簡言之，在j<v[i]的時候，不需要動。在j>=v[i]的時候，令f[j] = max(f[j],f[j - v[i]]+w[i])

所以我們只需要從>=v[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]);
    }    

二、完全背包問題

問題描述：

有 N 件物品和一個容量為 V 的背包，每件物品有各自的價值可以被選擇多次（0,1,2,3 … ），要求在有限的背包容量下，裝入的物品總價值最大。

樸素完全背包

1. 轉(zhuǎn)態(tài)f[i,j]定義 ：在前i個物品中選，總體積不超過j的最大價值。

2. 狀態(tài)轉(zhuǎn)移方程

   f[i,j] = max(f[i-1,j],f[i-1,j-v[i]]+w[i],f[i-1,j-2v[i]]+2w[i]…f[i-1,j-sv[i]]+sw[i])
   s表示能取到的最大值，不超過體積即可

   分析：

   ? 據(jù)題目要求，我們在考慮第i個物品的時候，我們可以不選，選1個，選2個。。?？梢赃x到選不下為止。在這些所有轉(zhuǎn)態(tài)中，我們找到一種最大情況。

代碼

for(int i = 1 ; i<=n ;i++)   //考慮每一件物品
    for(int j = 0 ; j<=m ;j++)  //考慮體積
        for(int k = 0 ; k*v[i]<=j ; k++)  //考慮當前物品在當前體積的情況下，能選到的最大價值
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

優(yōu)化一維的完全背包

1. 首先我們先來看如何優(yōu)化掉內(nèi)層循環(huán)

在上面樸素代碼最內(nèi)層的循環(huán)含義是找到放多個第i個物品可以可以使得當前體積獲得的價值最大，數(shù)學關(guān)系式如下：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)

f[i,j-v]如下：

f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , …)

我們發(fā)現(xiàn)上面兩個式子中，第一個式子的f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , … 可以用f[i,j-v]+w替換可得出如下遞推關(guān)系： f[i,j]=max(f[i,j-v]+w , f[i-1,j])

優(yōu)化一層循環(huán)后的代碼：

for(int i = 1 ; i <=n ;i++)
    for(int j = 0 ; j <=m ;j++)
    {
        f[i][j] = f[i-1][j];
        if(j-v[i]>=0)
            f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
    }

2. 01背包和完全背包的區(qū)別

? 這個代碼和01背包的代碼十分相似，唯一區(qū)別就是，01背包進行狀態(tài)計算的時候，每次用到的是上一層的狀態(tài)，而完全背包是用本層已經(jīng)更新的狀態(tài)去更新。

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]); //完全背包問題

3. 一維完全背包的優(yōu)化

? 這個優(yōu)化和01背包幾乎一致，唯一的區(qū)別 在于內(nèi)層循環(huán)的順序。為什么？ 參考上面

for(int i = 1 ; i<=n ;i++)
    for(int j = v[i] ; j<=m ;j++)//注意了，這里的j是從小到大枚舉，和01背包不一樣
     	f[j] = max(f[j],f[j-v[i]]+w[i]);

三、多重背包問題

問題描述：

有 N 件物品和一個容量為 V 的背包，每件物品有各自的價值可以被選擇多次但最多只能選擇S次，要求在有限的背包容量下，裝入的物品總價值最大。

樸素多重背包

1. 轉(zhuǎn)態(tài)f[i,j]定義 ：在前i個物品中選，總體積不超過j的最大價值。

2. 狀態(tài)轉(zhuǎn)移方程
   f[i,j] = max(f[i-1,j],f[i-1,j-v[i]]+w[i],f[i-1,j-2v[i]]+2w[i]…f[i-1,j-v[i]]+sw[i])
   s表示能取到的最大值，其中 s<=S 并且 s*v[i] <= j 。

3. 完全背包和多重背包的區(qū)別
   二者區(qū)別在于完全背包對于當前物品可以選無數(shù)個，直到背包裝不下為止。而多重背包是對完全背白的選擇進行了限制，每個物品只能選擇S個?？梢岳斫獬?mark>有限制的完全背包問題。

for(int i = 0;i<n;i++){
	for(int j = 0;j<=m;j++){
		for(int k = 0;k<=s[i] && k*v[i] <= j;k++){
			f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
		}
	}
}

多重背包的二進制優(yōu)化

1. 能不能用完全背包優(yōu)化方法來優(yōu)化呢？

• f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , … f[i-1,j-sv]+sw）
• f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2w , … f[i-1,j-sv]+(s-1)w , f[i-1,j-(s+1)v]+sw)

由于f[i,j-v]中多了一項f[i-1,j-(s+1)v]+sw，所以 f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , … f[i-1,j-sv]+sw 這一坨的最大值不能用f[i,j-v]+w表示，因此不能采用與完全背包同樣的方法優(yōu)化。

2. 二進制優(yōu)化的思想以及為什么用這種方法？

1）有一個數(shù)13，我們把13分成1，2，4，6 這四個數(shù)，我們可以拿這四個數(shù)可以表示任意1~13的數(shù)。

2）在清楚上一步之后，我們用上述思想轉(zhuǎn)換到本題。在正常背包的思路下，假設這一類物品有13個，我們要求出這一類物品的最大價值，需要考慮每一種情況，也就是枚舉14次（0~13)。假設我們現(xiàn)在將這13個物品打包成1,2,4,6,把他們看成4個單獨的物品，我們只需要考慮每件物品選與不選，就可以產(chǎn)生選0 ~ 13 其中的任意一種情況，而且只需要考慮4次。這就大大降低了我們枚舉的次數(shù)。

3）我們將每一類物品進行打包之后，我們對于打包之后的每一個物品的選與不選，可以轉(zhuǎn)化成01背包問題。

3. 最終實現(xiàn)代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 15000;
int n,m;
int logs[N],w[N];
int f[N];
int main()
{
	cin>>n>>m;
    int cnt = 0;
	for(int i = 0;i<n;i++){
		int a,b,s;  	//a體積，b表示價值 ,s表示該類物品的個數(shù)
        cin>>a>>b>>s;
        int t = 1;
        while(s >= t){  //將每一類物品按二進制數(shù)打包
            cnt++;
            logs[cnt] = t * a;
            w[cnt] = t * b;
            s -= t;
            t *= 2;
        }
        if(t > 0){     //不足，單獨算一個
            cnt++;
            logs[cnt] = s * a;
            w[cnt] = s * b;
        }
        
    }
    for(int i = 1;i<=cnt;i++){
		for(int j = m;j>=logs[i];j--){
			f[j] = max(f[j],f[j-logs[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

多重背包單調(diào)隊列優(yōu)化

1. f[i,j]當前最大價值是對于第i類物品，選擇0~S個(S是該類物品的最大個數(shù))這些情況下的價值的最大值

2. 根據(jù)上面的定義我們列出所有的情況。

 >f[i,j]=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...,f[i-1,j-kv]+kw);
 >f[i,j-v]=max(        f[i-1,j-v],  f[i-1,j-2v]+w, ...,f[i-1,j-kv]+(k-1)w,f[i-1,j-(k+1)v]+kw);
 >...
 >f[i,r] = max(...)  r = j - 能取到的最大物品個數(shù)k * v ，也可以理解成j % v 的余數(shù)

3. 對體積0~m，我們可以分為v組，每組大小s，對于任何一個 j = v*s+ r，所以我們可以得到一個容量為s的滑動串窗口。對于體積為m，并在第i類物品的選擇下的情況（即f[i,m]）

 f(i,r)=f[i,r]
 
 f(i,r+v)=max(f[i,r+v]-w,f[i,r])
 
 f(i,r+2v)=max(f[i,r+2v]-2w,f[i,r+v]-w,f[i,r])
 
 ?
 
 f(i,r+(s?1)v)=max(f[i,r+(s-1)v],f[i,r+(s - 2)v]+w,?,f[i,r]+(s?1)w)
 
 f(i,r+sv)=max(f[i,r+sv],f[i,r+(s-1)v]+w,?,f[i,r]+sw)               (滑動窗口已滿)
 
 f(i,r+(s+1)v)=max(f[i,r+(s+1)v],f[i,r+sv]+w,?,f[i,r+v]+sw)    (滑動窗口已滿)

?
 
 f(i,j?2v)=max(f[i,j?2v],f[i,j?3v]+w,?,f[i,j?(s+2)v]+sw)          (滑動窗口已滿)
 
 f(i,j?v)=max(f[i,j?v],f[i,j?2v]+w,?,f[i,j?(s+1)v]+sw)              (滑動窗口已滿)
 
 f(i,j)=max(f[i,j],f[i,j?v]+w,?,f[i, j?sv]+sw)                                (滑動窗口已滿)

4. 根據(jù)上面我們可以用一個單調(diào)隊列來維護我們需要用到的體積

• 當超過我們?nèi)萘縮的時候，隊頭彈出一個元素
• 當要插入的體積對應的最大值大于等于隊尾的最大值，要彈出隊尾，直到滿足為止
• 插入當前體積

5. 每次入隊的值是 dp[j-kv] + kw計算w的倍數(shù)，可以通過隊列存的體積與當前枚舉的體積之差模上v而得。

具體代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-463589.html

#include<bits/stdc++.h>
using namespace std;

const int N = 1010,M = 20010;  
int n,m;
int v[N],w[N],s[N];  //體積 價值 數(shù)量
int f[M],g[M];   	 //dp數(shù)組和備份數(shù)組
int q[M];   		 //維護滑動窗口的單調(diào)隊列
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i = 1;i<=n;i++){
        memcpy(g,f,sizeof f);
        for(int j = 0;j<v[i];j++){    //分成v[i]組
            int hh = 0,tt = -1;
            for(int k = j;k<=m;k += v[i]){
                while (hh <= tt && k - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && g[q[tt]] + (k - q[tt])/v[i] * w[i] <= g[k]) tt--;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
    
}

到了這里，關(guān)于背包問題分析代碼詳解【01背包+完全背包+多重背包】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！