背包模型

• 前言
• • 背包問(wèn)題的初始化問(wèn)題
• 01背包
• • 裝箱問(wèn)題
  • 寵物小精靈之收服
  • 數(shù)字組合
  • 開(kāi)心的金明
  • 01背包+貪心
• 背包問(wèn)題求解方案數(shù)
• • 貨幣系統(tǒng)
• 貨幣系統(tǒng)Ⅱ
• 多重背包問(wèn)題
• • 慶功會(huì)
• 混合背包問(wèn)題
• 二維費(fèi)用的背包問(wèn)題
• • 二維費(fèi)用的背包問(wèn)題
• 潛水員
• 分組背包問(wèn)題
• • 分組背包
  • 機(jī)器分配（每一組只取一個(gè)）
  • 金明的預(yù)算方案（每一組里能取多個(gè)）
• 背包求解最優(yōu)方案數(shù)
• 背包求解具體方案

前言

對(duì)于原始背包問(wèn)題及其優(yōu)化可以參見(jiàn)這篇博客
背包問(wèn)題

背包問(wèn)題的初始化問(wèn)題

一般問(wèn)題有以下三種情況

對(duì)應(yīng)的初始化方法

對(duì)于體積最多是j，$f[0][j]$表示一個(gè)物品都不選體積最多是j的情況，這個(gè)是存在的，所以置為0 ，對(duì)于循環(huán)中我們是最多是j，如果 v < 0 ,說(shuō)明 v1 > j ，這是不存在的。

對(duì)于體積恰好是j，$f[0][j]$表示一個(gè)物品都不選體積最多是j的情況，只有$f[0][0]$是存在的，其余的都是這個(gè)是不存在的，因此設(shè)置為一個(gè)不合法的數(shù)，至于是正無(wú)窮還是負(fù)無(wú)窮，取決于題目是求最大還是最小；對(duì)于循環(huán)邊界理由和上面一樣

對(duì)于初始化條件與第2個(gè)一樣 ；對(duì)于循環(huán)條件，我們·是至少是j因此當(dāng)v<0的時(shí)候是存在的，而它們的值是 v = 0 時(shí)候的值。

01背包

裝箱問(wèn)題

題目轉(zhuǎn)送門

個(gè)人解題思路：

這題是讓我們盡可能的讓背包的剩余空間小，也就是放入的物品的體積要盡可能的大，因?yàn)槲锲分唤o了體積沒(méi)有價(jià)值，那么我們就可能將每一個(gè)物品的價(jià)值等同于它的體積，那么這就轉(zhuǎn)變?yōu)榱?1背包問(wèn)題。那么這個(gè)$dp[i]$表示總體積不超過(guò)背包容量下的最大體積，也就說(shuō)剩余體積最小。

代碼：

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

寵物小精靈之收服

題目轉(zhuǎn)送門

解題思路：

這題由單一花費(fèi)變成了二維花費(fèi)，我們的花費(fèi)有精靈球的數(shù)量和體力，因此我們定義的是二維dp；$dp[i][j][k]$表示考慮前i個(gè)精靈，精靈球數(shù)量不超過(guò)j，體力不超過(guò)k的最大的精靈球數(shù)量。由背包問(wèn)題我們可以將第一維的空間省略掉，采用逆序的遍歷方式。對(duì)于二維我們還是有

對(duì)于剩余的體力，我們?cè)?span id="ze8trgl8bvbq" class="katex--inline">$f[N][1?M]$中選出等于$f[N][M]$的最小的體力，這是花費(fèi)的最小體力。同時(shí)因?yàn)轶w力不能會(huì)0，我們?cè)贉p1.

代碼：

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

數(shù)字組合

題目轉(zhuǎn)送門

解題思路;

這是一個(gè)典型的0/1背包模型，N個(gè)正整數(shù)就是N個(gè)物品，M就是背包的容積。在外層循環(huán)到i時(shí)(表示從前i個(gè)數(shù)中選)，設(shè)F[j]表示“和為j”有多少種方案。在具體實(shí)現(xiàn)中，只需要把原始代碼中求max的函數(shù)改為求和即可。
代碼：

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

開(kāi)心的金明

題目轉(zhuǎn)送門

解題思路:

這題我們可以將每一個(gè)物品的錢看成是體積，而物品的價(jià)值則是金額*重要程度。這樣我們就轉(zhuǎn)化成了01背包問(wèn)題了、

代碼;

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

01背包+貪心

題目轉(zhuǎn)送門

解題思路：

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 10010; int n , m ; int f[N]; struct Stone{int s , e ,l;bool operator < (const Stone & w)const {return s * w.l < w.s * l;} }stone[N];int main(){int T;cin>>T;for(int C = 1 ; C <= T ; ++C){m = 0;cin>>n;for(int i = 0 ; i < n ; ++i){int s ,e ,l;cin >>s>>e>>l;stone[i] = {s ,e,l};m += s;}sort(stone , stone + n);memset(f , -0x3f , sizeof f);f[0] = 0;for(int i = 0 ; i < n ; ++i){int s = stone[i].s , e = stone[i].e , l = stone[i].l;for(int j = m ; j >= s ; --j)f[j] = max(f[j] , f[j-s] + e - (j - s)*l);}int res = 0;for(int i = 0 ; i <= m ; ++i)res = max(res , f[i]);cout<<"Case #"<<C<<": "<<res<<endl;}return 0; }

背包問(wèn)題求解方案數(shù)

貨幣系統(tǒng)

題目轉(zhuǎn)送門

解題思路·:

這題和上面的數(shù)字組合不同的地方在于數(shù)字組合是每一個(gè)數(shù)字只能選一次，而在這里每一個(gè)貨幣可以選多次，因此這就是一個(gè)完全背包的模板題，在具體實(shí)現(xiàn)中，只需要把原始代碼中求max的函數(shù)改為求和即可。

代碼：

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

貨幣系統(tǒng)Ⅱ

題目轉(zhuǎn)送門

解題思路;

等價(jià)類有以下三種性質(zhì)，

因此我們要考慮的是對(duì)于每一個(gè)a[i]查詢其是否會(huì)被a中其他不含它的數(shù)組成，如果不可以我們就要選它，如果可以就不選。那么如何知道呢？那這就是一個(gè)和上一題一樣的問(wèn)題了，我們處理完后，對(duì)于每一個(gè)a[i]如果其$f[a[i]]!=1$那么說(shuō)明這個(gè)數(shù)不能由別的數(shù)組成

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 110 , M = 25010; int n , m ; int f[M] , w[N];int main(){int T;cin>>T;while(T--){cin>>n;memset(f , 0 , sizeof f);f[0] = 1;for(int i = 1 ;i <= n ; ++i){cin>>w[i];for(int j = w[i] ; j <= M ; ++j)f[j] += f[j-w[i]];}int cnt = 0;for(int i = 1; i <= n ;++i)if(f[w[i]] == 1)cnt++;cout<<cnt<<endl;}return 0; }

多重背包問(wèn)題

慶功會(huì)

題目轉(zhuǎn)送門

解題思路：

我們把撥款金額看成背包容積，價(jià)格看成物品體積，價(jià)值看成物品價(jià)值，那么這個(gè)題目就是一個(gè)多重背包的裸題。對(duì)于這個(gè)數(shù)據(jù)范圍我們可以使用二進(jìn)制優(yōu)化的多重背包來(lái)求解。

多重背包詳細(xì)解釋

代碼：

#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 510 , M = 6010; int n , m; int f[M]; struct Good{int w , v; }; vector<Good>goods;int main() {cin>>n>>m;for(int i = 1; i <= n ; ++i){int w ,v , s;cin>>w>>v>>s;for(int k = 1 ; k <= s; k *= 2){s -= k;goods.push_back({k*w,k*v});}if(s > 0)goods.push_back({s*w,s*v});}for(auto good : goods)for(int j = m ; j >= good.w ; --j)f[j] = max(f[j] ,f[j-good.w] + good.v);cout<<f[m]<<endl;return 0; }

混合背包問(wèn)題

題目轉(zhuǎn)送門

解題思路：

我們回顧背包問(wèn)題的表達(dá)式：$dp[i][j]$表示對(duì)于前i個(gè)物品，總體積不超過(guò)j的最大價(jià)值。我們發(fā)現(xiàn)它對(duì)于物品的類型是沒(méi)有限定的。不同類型的物品，我們只是在狀態(tài)計(jì)算的時(shí)候是不一樣的。同時(shí)對(duì)于第i個(gè)物品我們當(dāng)前只會(huì)考慮第i個(gè)物品而不用考慮前i-1個(gè)物品的情況。因此這題我們對(duì)于第i個(gè)物品，按照其類型來(lái)進(jìn)行對(duì)應(yīng)的狀態(tài)計(jì)算。

代碼：

#include<iostream> #include<algorithm> using namespace std; const int N = 1010; int n , m; int f[N];int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i){int v , w ,s;cin>>w>>v>>s;if(s == 0)// 完全背包{for(int j = w ; j <= m ; ++j)f[j] = max(f[j] ,f[j-w] + v);}else{if(s == -1)s = 1;for(int k = 1 ; k <= s ; k *= 2){s -= k;for(int j = m ; j >= k * w ; --j)f[j] = max(f[j] , f[j-k*w] + k*v);}if(s)for(int j = m ; j >= s*w ; --j)f[j] = max(f[j] , f[j-s*w] + s*v);}}cout<<f[m]<<endl;return 0; }

二維費(fèi)用的背包問(wèn)題

二維費(fèi)用的背包問(wèn)題

題目轉(zhuǎn)送門

解題分析：

代碼：

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

潛水員

題目轉(zhuǎn)送門

解題思路：

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 100; int n,m , k; int f[N][N];int main(){cin>>n>>m>>k;memset(f , 0x3f , sizeof f);f[0][0] = 0;for(int i = 1 ; i <= k ; ++i){int w1 ,w2 ,c;cin>>w1>>w2>>c;for(int j = n ; j >= 0 ; --j)for(int k = m ; k >= 0 ; --k)f[j][k] = min(f[j][k] ,f[max(0,j-w1)][max(0,k-w2)] + c);}cout<<f[n][m]<<endl;return 0; }

分組背包問(wèn)題

分組背包

對(duì)于分組背包，每一組的物品可以選與不選，如果選，一組物品中只能選一個(gè)。那么到這里我們可以知道在每一組內(nèi)部的選法類似于01背包，那么我們有如下分析

for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)for(int k=1;k<=s[i];k++)//s[i]表示第i組物品的個(gè)數(shù)if(j>=v[i][k])//剩余的背包容量j大于第i組的第k個(gè)物品的體積 {f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}

機(jī)器分配（每一組只取一個(gè)）

機(jī)器分配

解題思路：
我們將問(wèn)題抽象一下，將公司看成是一組物品，公司中的物品數(shù)量為m，每一個(gè)物品體積為j j ， 價(jià)值為g[i][j] 。對(duì)于方案我們逆序遍歷每一組，對(duì)于每一組我們依據(jù)dp計(jì)算式子來(lái)找到對(duì)應(yīng)的數(shù)量。

代碼：

#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 155; int n ,m; int f[N][N] , g[N][N]; int ans[N]; int main(){cin>>n>>m;for(int i = 1 ; i <= n ; ++i)for(int j = 1; j <= m ; ++j)cin>>g[i][j];for(int i = 1 ; i <= n ; ++i) // 組數(shù)for(int j = 1; j <= m ; ++j) // 體積 for(int k = 0 ; k <= j ; ++k) // 決策 ， 可以從0開(kāi)始表示一個(gè)都不選f[i][j] = max(f[i][j] ,f[i-1][j- k] + g[i][k]);cout<<f[n][m]<<endl;int res = f[n][m] , s = m ; // s是當(dāng)前剩余的總可以體積for(int i = n ; i >= 1 ; --i)for(int k = 0 ; k <= s ; ++k)if(res == f[i-1][s-k] + g[i][k]){ans[i] = k;s -= k; //體積減少res -= g[i][k]; // 價(jià)值減少break;}for(int i = 1 ; i <= n ;++i)cout<<i<<" "<<ans[i]<<endl;return 0; }

金明的預(yù)算方案（每一組里能取多個(gè)）

題目轉(zhuǎn)送門

解題思路：

對(duì)于每一組中選多個(gè)的情況我們可以用二進(jìn)制來(lái)枚舉每一種可能。同時(shí)本題的一個(gè)難點(diǎn)是如何分好組。我們可以利用vector來(lái)解決（詳細(xì)看代碼）

代碼：

#include <cstring> #include <iostream> #include <algorithm> #include <vector>#define w first #define v secondusing namespace std;typedef pair<int, int> PII;const int N = 60, M = 32010;int n, m; PII master[N]; vector<PII> sv[N]; int f[M];int main(){cin>>m>>n;for(int i = 1 ; i <= n ; ++i){int w , v ,q;cin>>w>>v>>q;if(!q)master[i] = {w , w*v};else sv[q].push_back({w,w*v});}for(int i = 1 ; i <= n ; ++i){if(master[i].first)for(int j = m ; j >= 0 ; --j){int len = sv[i].size();for(int k = 0 ; k < 1 << len;++k){int w = master[i].first , v = master[i].second;for(int u = 0; u < len;++u)if( k >> u & 1) w += sv[i][u].w , v += sv[i][u].v;if(j >= w)f[j] = max(f[j] , f[j-w] + v);}}}cout<<f[m]<<endl;return 0; }

背包求解最優(yōu)方案數(shù)

題目轉(zhuǎn)送門

之前我們求的方案數(shù)是只考慮了體積，表示的是裝滿背包的方案數(shù)。而這題是求的是最優(yōu)解（最大值）的方案數(shù)。

代碼：

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

背包求解具體方案

題目轉(zhuǎn)送門

解題思路：
一般來(lái)說(shuō)求方案的話，一種方法是倒推和在dp的時(shí)候記錄。這里我們依據(jù)01背包的式子進(jìn)行倒推。

代碼：

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

然后有一些數(shù)據(jù)被卡了，發(fā)現(xiàn)題目要的是字典序最小，這就是很惡心了。一般對(duì)于字典序最小我們都是通過(guò)貪心來(lái)解決。對(duì)于這題就是從前往后詢問(wèn)每一個(gè)物品，

如果按照平時(shí)的背包問(wèn)題我們是從前往后遍歷的，那么我們?cè)诘雇频臅r(shí)候就需要從后往前這樣就不符合貪心的原則了。因此我們?cè)赿p的時(shí)候倒著堆。$dp[i][j]$表示從第i個(gè)物品開(kāi)始體積不超過(guò)j的最大價(jià)值。

代碼：

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

總結(jié)

以上是生活随笔為你收集整理的动态规划之背包模型及其扩展应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。