本文主要是介绍背包九讲 11题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
聚聚视频讲的太好了
前六讲 最后三讲
题目全在这了
01背包问题
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e3+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N],n,m;
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,v,w;i<=n;++i){cin>>v>>w;for(int j=m;j>=v;--j) dp[j]=max(dp[j],dp[j-v]+w);}cout<<dp[m]<<endl;return 0;
}完全背包
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e3+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N],n,m;
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,v,w;i<=n;++i){cin>>v>>w;for(int j=v;j<=m;++j) dp[j]=max(dp[j],dp[j-v]+w);}cout<<dp[m]<<endl;return 0;
}
多重背包问题 I
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=105;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N],n,m;
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,v,w,s;i<=n;++i){cin>>v>>w>>s;for(int j=m;j>=v;--j){for(int k=0;k<=s && k*v<=j;++k){dp[j]=max(dp[j],dp[j-k*v]+k*w);}}}cout<<dp[m]<<endl;return 0;
}
多重背包问题 II
二进制拆分优化，然后作为01背包来考虑即可，将s拆成2进制表示，最后多的那个部分单独拿出来。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=2e3+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
struct node{int v,w;
};
vector<node> a;
int n,m,dp[N];
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,v,w,s;i<=n;++i){cin>>v>>w>>s;for(int k=1;k<=s;k*=2){a.pb({v*k,w*k});s-=k;}if(s) a.pb({v*s,w*s});} for(auto it:a){int v=it.v,w=it.w;for(int j=m;j>=v;--j) dp[j]=max(dp[j],dp[j-v]+w);}cout<<dp[m]<<endl; return 0;
}多重背包问题 III
单调队列优化，对于一个体积为v的物品，我们考虑到他的更新，将体积%v的值进行分组，一个组之间才会有递推关系，而不同的组之间是不会有更新和递推关系的。考虑对于一个dp[j] 是从上一层dp[j-v]+w,dp[j-2*v]+2*w…….更新来，那对于dp[j+v]就是从上一层dp[j]+w，dp[j-v]+2*w…..更新而来，其实就是对于dp[j],dp[j+v]就是平移的一格，然后总体+w；但是原来数的大小关系并没有发生改变，所以这里用单调队列维护即可，只是加的x*w发生了改变，这个我们可以通过计算与j差几个v，就可以得出了嘛。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=2e5+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m,dp[N][2],q[N];
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;bool fg=0;int tt=-1,hh=0; for(int i=1,v,w,s;i<=n;++i){cin>>v>>w>>s;for(int j=0;j<v;++j){//将体积按%v的值进行分类 tt=-1,hh=0;for(int k=j;k<=m;k+=v){dp[k][fg]=dp[k][fg^1];while(hh<=tt && k-s*v>q[hh]) hh++;if(hh<=tt) dp[k][fg]=max(dp[k][fg],dp[q[hh]][fg^1]+(k-q[hh])/v*w);while(hh<=tt && dp[q[tt]][fg^1]-(q[tt]-j)/v*w <= dp[k][fg^1]-(k-j)/v*w) tt--; q[++tt]=k;} }fg^=1;}cout<<dp[m][fg^1]<<endl;return 0;
}
混合背包问题
即包含了01背包，完全背包和多重背包，这里可以将多重背包拆分成01背包，然后我们只需要考虑01背包和完全背包，这里两个注意循环的方向即可。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e3+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N],n,m;
struct node{int type,v,w;
};
vector<node> a;
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,v,w,s;i<=n;++i){cin>>v>>w>>s;if(s==-1) a.pb({-1,v,w});//01背包 else if(s==0) a.pb({0,v,w});//多重背包 else{//完全背包拆成01背包 for(int k=1;k<=s;k*=2){a.pb({-1,v*k,w*k});s-=k; } if(s) a.pb({-1,v*s,w*s});}}int v,w;for(auto it:a){v=it.v,w=it.w;if(it.type==-1){for(int i=m;i>=v;--i) dp[i]=max(dp[i],dp[i-v]+w);}else{for(int i=v;i<=m;++i) dp[i]=max(dp[i],dp[i-v]+w);}} cout<<dp[m]<<endl;return 0;
}
二维费用的背包问题
多了一维重量，这里直接考虑多循环一层重量即可，01背包从大到小进行更新即可。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e3+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N][N],n,V,M;
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>V>>M;for(int i=1,v,m,w;i<=n;++i){cin>>v>>m>>w;for(int j=V;j>=v;--j){for(int k=M;k>=m;--k){dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);}} }cout<<dp[V][M]<<endl;return 0;
}
分组背包问题
多一重循环，来判断选这一组里的哪一个
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e2+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m,v[N],w[N],dp[N];
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,s;i<=n;++i){cin>>s;for(int j=1;j<=s;++j) cin>>v[j]>>w[j];for(int j=m;j>=0;--j){for(int k=1;k<=s;++k){if(j>=v[k]) dp[j]=max(dp[j],dp[j-v[k]]+w[k]);}}}cout<<dp[m]<<endl;return 0;
}
有依赖的背包问题
dp[i][j]:当选i为节点，空间不大于j的最大值
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e2+5;
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N][N];//dp[i][j]:当选i为节点，空间不大于j的最大值
int n,m,v[N],w[N],root;
vector<int> G[N];
il void dfs(int u){for(auto son:G[u]){dfs(son);for(int j=m-v[u];j>=0;--j){//给u空出v[u]空间，剩下的分给儿子 for(int k=0;k<=j;++k){dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);}}}for(int j=m;j>=v[u];--j) dp[u][j]=dp[u][j-v[u]]+w[u];for(int j=v[u]-1;j>=0;--j) dp[u][j]=0;
}
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,np;i<=n;++i){cin>>v[i]>>w[i]>>np;if(np==-1) root=i;else G[np].pb(i);}dfs(root);cout<<dp[root][m]<<endl;return 0;
}背包问题求方案数
这里初始化不能随便的默认为0了，因为这里需要更新方案数，前面的dp[i]表示体积不大于i的最大价值，（这和全部初始化为0有关，因为如果当空间为k时取得最大价值，因为我们将dp[m-k]初始化为0，所以也可以得到最值，但实际空间不为m）这样的话不利于更新方案数。现在初始话只将dp[0]定义为0，其他的定义为-inf，dp[i]表示空间恰好为i时的最大价值，这样是符合实际情况的，最后的mx是要扫一遍数组的，因为最大价值并不一定在最大空间取得。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e3+5;
il int Add(int &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(int &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int dp[N],num[N];
//dp[i]:体积为i时的最大价值，num[i]:满足体积为i最大价值的方案数
int n,m;
int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;num[0]=1;for(int i=1;i<=m;++i) dp[i]=-inf;for(int i=1,v,w;i<=n;++i){cin>>v>>w;for(int j=m;j>=v;--j){int mx,mxnum=0;mx=max(dp[j],dp[j-v]+w);if(mx==dp[j]) Add(mxnum,num[j]);if(mx==dp[j-v]+w) Add(mxnum,num[j-v]);dp[j]=mx,num[j]=mxnum;}}int ans=-inf,all=0;for(int j=0;j<=m;++j) ans=max(ans,dp[j]);for(int j=0;j<=m;++j){if(dp[j]==ans) Add(all,num[j]);}cout<<all<<endl;return 0;
}
背包问题求具体方案
因为题目要求字典序，所以i从大到小着来，然后从1到n从小到大贪心的考虑。视频中代码少加了一个nv-v[i]的判断。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=1e3+5;
//il int Add(int &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(int &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int n,m,dp[N][N],v[N],w[N];int main(){std::ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;++i) cin>>v[i]>>w[i];//从后往前更新 for(int i=n;i>=1;--i){for(int j=0;j<=m;++j){if(j>=v[i]) dp[i][j]=max(dp[i+1][j],dp[i+1][j-v[i]]+w[i]);else dp[i][j]=dp[i+1][j];}}int nv=m;for(int i=1;i<=n;++i){if(nv-v[i]>=0 && dp[i][nv]==dp[i+1][nv-v[i]]+w[i]){cout<<i<<" ";nv-=v[i];}}return 0;
}
这篇关于背包九讲 11题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
