藍橋杯備賽背包問題

背包問題

![[背包問題.png]]

01背包

1.題意概要：有 $n$ 個物品和一個容量為 $V$ 的背包，每個物品有重量 $w_i$ 和價值 $v_i$ ?兩種屬性，要求選若干物品放入背包使背包中物品的總價值最大且背包中物品的總重量不超過背包的容量。
要求:每個物品只能拿一次,所以每個物品只有拿或不拿兩種狀態，故稱01背包
2.狀態:dp[i][j]表示到第i個物品為止(不一定拿)，到容量j為止，背包的最大價值
狀態轉移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)(注意先判斷j>=w)(不關心有沒有拿，只關心最大價值)
最終狀態:dp[n][V]

小明的背包1

學習:
(1)模版題，可以不用開w[i],v[i]數組記錄，反正是一個一個物品枚舉的
代碼:

#include <bits/stdc++.h>using namespace std;const int N=1e2+10,V=1e3+10;
int n,vol,dp[N][V];int main(){ios::sync_with_stdio(false);cin>>n>>vol;for(int i=1;i<=n;i++){int w,v;cin>>w>>v;for(int j=1;j<=vol;j++){//判斷是否越界，即能不能放下第i個物品 if(j>=w)	dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);else dp[i][j]=dp[i-1][j];}}cout<<dp[n][vol];return 0;
}

01背包一維滾動數組優化

學習:
(1)二維數組的第一維度dp[i]和dp[i-1]本質就是第i-1層的值來轉移給第i層，就是用遍歷i來實現的，因此可以優化為滾動一維數組，讓前面的舊值轉移給后面的新值，所以一個維度dp[j]就夠了，表示背包容量到j為止的最大價值,狀態轉移方程:
dp[j]=max(dp[j],dp[j-w]+v)
(2)背包容量倒序遍歷，從 $V$ 開始 $w_i$ ,原因如下圖:
![[01背包優化圖.png]]
黃色塊為舊值，綠色塊為新值，左側二維dp[i]的綠色新值都是由dp[i-1]黃色舊值轉移而來，所以背包容量從前往后或從后往前無所謂，而右側一維只能是黃色舊值轉移給綠色新值，所以從后往前遍歷，遇到個新值dp[j],從前面的舊值dp[j-w]轉移過來，如果從前往后遍歷，會出現dp[j-w2]由dp[j-w2-w1]轉移過一次，變成新值(不再是舊值dp[j-w2])，dp[j]由新值dp[j-w2]轉移過來，相當于加上了兩次物品，例如:

        w    v
物品
1       1    2
j                0  1  2
dp[j](從前往后)   0  2  4(出現問題，考慮了兩次物品1)
dp[j](從后往前)   0  2  2

小明的背包1優化代碼

#include <bits/stdc++.h>using namespace std;
const int V=1e3+10;
int n,vol,dp[V];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>vol;for(int i=1;i<=n;i++){int w,v;cin>>w>>v;for(int j=vol;j>=w;j--){ //倒序遍歷 dp[j]=max(dp[j],dp[j-w]+v);}}cout<<dp[vol];return 0;
}

背包與魔法

學習:
(1)這題是01背包的變體，因為多了一個是否使用魔法，且最多使用一次，就相當于狀態dp多了一個維度的變量(這個思想很重要),就有兩大種狀態dp[j][0],dp[j][1],三種狀態轉移:1.不加入物品2.加入物品不使用魔法3.加入物品使用魔法，以及相應的狀態轉移方程

//不使用魔法,一般的一維01背包
dp[j][0]=max(dp[j][0],dp[j-w][0]+v); 
dp[j][1]=max(dp[j][1],dp[j-w][1]+v);
//使用魔法
if(j>=(w+k))	dp[j][1]=max(dp[j][1],dp[j-(w+k)][0]+2*v);//精華所在

(2)狀態轉移方程在同一個反向遍歷j下轉移，表示對當前物品的轉移，因為j最小到w，所以第二種狀態轉移方程要有個判斷j>=(w+k)
(3)求多個元素的最大值，中間套個列表({})即可
maxn=max({1,2,3,4})
代碼:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=2e3+10,M=1e4+10;
int n,m,k;
ll dp[M][2]; //第一維度為背包重量j，第二維度表示是否使用魔法 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>k;for(int i=1;i<=n;i++){	int w,v;cin>>w>>v;	for(int j=m;j>=w;j--){//不使用魔法,一般的一維01背包dp[j][0]=max(dp[j][0],dp[j-w][0]+v); dp[j][1]=max(dp[j][1],dp[j-w][1]+v);//使用魔法if(j>=(w+k))	dp[j][1]=max(dp[j][1],dp[j-(w+k)][0]+2*v); }}cout<<max(dp[m][0],dp[m][1]);return 0;
}

完全背包

(1)特征:每個物品有無限多個，可以被拿無限多次
(2)狀態dp[j]表示到體積j為止的最大價值狀態轉移方程:
dp[j]=max(dp[j],dp[j-w]+v)跟一維01背包類似，但是不同點在于完全背包要從前往后遍歷，這樣每個物品能被拿無限多次，用新數據來更新新數據，而一維01背包要從后往前遍歷，確保每個物品只拿一次，用舊數據來更新新數據

小明的背包2

學習:
(1)模版題
代碼:

#include <bits/stdc++.h>using namespace std;
const int V=1e3+10;
int n,vol,dp[V];int main(){ios::sync_with_stdio(false);cin>>n>>vol;for(int i=1;i<=n;i++){int w,v;cin>>w>>v;for(int j=w;j<=vol;j++){ //正序遍歷 dp[j]=max(dp[j],dp[j-w]+v);}}cout<<dp[vol];return 0;
}

多重背包

(1)特征:第i個物品有 $s_i$ 個，共有s+1種狀態(取0,1,2…s個)
(2)核心解決辦法:將 $s_i$ 個第i個物品當成獨立的s個物品(遍歷s次即可)，每個 $s_ij$ 物品就只有一個，就是01背包問題了

小明的背包3

學習:
(1)多重背包模版題
代碼:

#include <bits/stdc++.h>using namespace std;
const int V=2e2+10;
int n,vol,dp[V];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>vol;for(int i=1;i<=n;i++){int w,v,s;cin>>w>>v>>s;//遍歷s次，相當于把第i個物品拆成s個i_s物品，每個i_s物品只有一個，為01背包問題for(int k=1;k<=s;k++){//01背包倒序遍歷 for(int j=vol;j>=w;j--){dp[j]=max(dp[j],dp[j-w]+v);}} }cout<<dp[vol];return 0;
}

二進制優化多重背包

(1)將s個物品拆分成s組，每組一個的經典多重背包時間復雜度為O(n*s*V),s過大會超時
(2)因為任意一個數都有其對應的二進制數，令s=1+2+4+8+…+其他，一個物品可以分為約log2(s)組,就可以將幾個二進制數組合表示0-s這s+1種中的任意狀態，例如:
s=14=1+2+4+7(其他)，要取10個物品，就相當于依次取1,2,7個物品即可,
所以可以將物品數量拆分為多個二進制組合，減少狀態轉移次數
(3)修改s的遍歷即可，不再是1個1個加，而是倍數乘,而2個物品對應修改為2w,2v即可,最終的復雜度為O(n*log2(s)*V)

新一的寶藏搜尋加強版

學習:
(1) $s_i$ 最大能到2e4，普通多重背包會超時，需要二進制優化,記得最后一個剩余的數要單獨遍歷一次
代碼:

#include <bits/stdc++.h>using namespace std;
const int V=2e4+10;
int n,vol,dp[V];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>vol;for(int i=1;i<=n;i++){int w,v,s;cin>>w>>v>>s;int t=0;//t為二進制數累加和 for(int k=1;(k+t)<=s;k*=2){t+=k;//01背包倒序for(int j=vol;j>=k*w;j--){dp[j]=max(dp[j],dp[j-k*w]+k*v);}}//最后剩余部分為s-t for(int j=vol;j>=(s-t)*w;j--){dp[j]=max(dp[j],dp[j-(s-t)*w]+(s-t)*v);}}cout<<dp[vol];return 0;
}

二維費用背包

(1)特征:物品除了價值v,體積w兩個特征外，還多了一個重量m特征，現在有兩個限制條件:體積不超過W和重量不超過M的最大價值
(2)解決方法:一維01背包變成二維即可，仍然倒序更新，dp[i][j]表示體積到i為止，重量到j為止的最大價值,狀態轉移方程:dp[i][j]=max(dp[i][j],dp[i-w][j-m]+v)

小藍的神秘行囊

學習:
(1)二維費用背包模版題
代碼:

#include <bits/stdc++.h>using namespace std;
const int V=105,M=105;
int n,vol,mm,dp[V][M];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>vol>>mm;for(int i=1;i<=n;i++){int v,m,w;cin>>v>>m>>w;//二維倒序遍歷for(int j=vol;j>=v;j--){for(int k=mm;k>=m;k--){dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);}}}cout<<dp[vol][mm];return 0;
}

分組背包

(1)特征:共有n組物品，每組物品里面有s個物品，每個物品有對應的w和v，每組物品最多只能取一個(區別所在),所有狀態轉移的第一維度是組，且沒用一維優化，因為每一組的w和v有多個，不是固定的
(2)解決問題:dp[i][j]表示到第i組為止，體積j為止的最大價值,狀態轉移方程(好好理解)

dp[i][j]=dp[i-1][j] //初始化這一組都不取，就是上一組的狀態(01背包是通過一個狀態轉移方程全做了)
dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v) //注意第一個是dp[i][j]，而不是dp[i-1][j],因為每一組最多取一個物品，相當于比較取第i組取之前某個物品的最大價值(dp[i][j])和第i組取當前這個物品的最大價值(dp[i-1][j-w]+v)相比較

(3)正序倒序無所謂，因為兩個維度了

小明的背包5

代碼:

#include <bits/stdc++.h>using namespace std;
const int N=105,V=105;
int n,vol,dp[N][V];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>vol;//遍歷每一組for(int i=1;i<=n;i++){int s;cin>>s;//這一組商品都不拿,等價于初始化dp[i][j] for(int j=0;j<=vol;j++)	dp[i][j]=dp[i-1][j]; //遍歷每一組的每一個物品,考慮拿不拿 while(s--){int w,v;cin>>w>>v;//從上一組轉移過來，而不是從上一個物品轉移過來 for(int j=w;j<=vol;j++){dp[i][j]=max(dp[i][j],dp[i-1][j-w]+v); //第一個是dp[i][j],保證每一組最多取一個物品 }} } cout<<dp[n][vol];return 0;
}

藍橋杯真題

砝碼稱重

學習:
(1)不是典型的背包問題，但是將動態規劃的思想運用的淋漓盡致
首先定義一個狀態:dp[i][j]表示到第i個砝碼為止，到重量j為止，是否可以稱出重量j，為0/1,
再考慮i和j的邊界，i最多到n，而j最多到sum，不是到V
再考慮它由哪幾種狀態轉移而來:
1.不拿砝碼，由dp[i-1][j]轉移而來
2.拿砝碼放左側，由dp[i-1][abs(j-w)](放左側相當于加上w，由于鏡像,abs(j-w)->j)
3.拿砝碼放右側,由dp[i-1][j+w]轉移而來(放右側相當于減去w，j+w->j)
![[砝碼稱重.png]]
代碼:
(1)法一:好理解

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=105,V=1e5+10;
int n,w[N],dp[N][V];//dp[i][j]表示到第i個砝碼為止，到重量j為止，是否可以稱出來，為0/1 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;ll sum=0;for(int i=1;i<=n;i++){cin>>w[i];sum+=w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=sum;j++){ //最大重量到sum //1.好理解的//先從前i-1個砝碼狀態轉移過來dp[i][j]=dp[i-1][j];//如果上一個狀態稱不出來重量j，看看有了第i個砝碼能不能稱出重量jif(dp[i][j]==0){//當前砝碼就是重量jif(w[i]==j)	dp[i][j]=1;//重量j+w[i]能稱出來，當前砝碼放另一側，減去w[i],j+w[i]->j if(dp[i-1][j+w[i]])	dp[i][j]=1;//重量abs(j-w[i])能稱出來，當前砝碼放同側,加上w,abs(j-w[i])->j //取abs是因為不確定對于自己這一側來看重量是正是負(自己這一側為正值)if(dp[i-1][abs(j-w[i])])	dp[i][j]=1; } }} ll ans=0;for(int j=1;j<=sum;j++){if(dp[n][j]==1)	ans++;}cout<<ans;return 0;
}

(2)法二:

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=105,V=1e5+10;
int n,w[N],dp[N][V];//dp[i][j]表示到第i個砝碼為止，到重量j為止，是否可以稱出來，為0/1 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;ll sum=0;for(int i=1;i<=n;i++){cin>>w[i];sum+=w[i];}dp[0][0]=1; //保證當前砝碼就是重量j的情況for(int i=1;i<=n;i++){for(int j=0;j<=sum;j++){ //從0開始,最大重量到sum //2.三種狀態轉移而來,且dp[i][j]值為0或1，用或操作dp[i][j]=dp[i-1][j]||dp[i-1][j+w[i]]||dp[i-1][abs(j-w[i])];}} ll ans=0;for(int j=1;j<=sum;j++){ //從1開始if(dp[n][j]==1)	ans++;}cout<<ans;return 0;
}