背包问题
2019-10-08 08:48:04来源:博客园 阅读 ()
背包问题
01背包
n个物品,v的体积,求最多能装下的价值
每个物品只能拿一次
https://www.acwing.com/problem/content/2/
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 int N,V,dp[1005] = {0}; 5 scanf("%d%d",&N,&V); 6 for(int i=1,x,y;i<=N;i++){ 7 scanf("%d%d",&x,&y); 8 for(int j=V;j>=x;j--){ 9 dp[j] = max(dp[j],dp[j-x]+y); 10 } 11 } 12 printf("%d\n",dp[V]); 13 return 0; 14 }代码
完全背包
n个物品,v的体积,求最多能装下的价值
每个物品可以拿无限次
https://www.acwing.com/problem/content/3/
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 int N,V,dp[1005] = {0}; 5 scanf("%d%d",&N,&V); 6 for(int i=1,x,y;i<=N;i++){ 7 scanf("%d%d",&x,&y); 8 for(int j=x;j<=V;j++){ 9 dp[j] = max(dp[j],dp[j-x]+y); 10 } 11 } 12 printf("%d\n",dp[V]); 13 return 0; 14 }代码
多重背包
n个物品,v的体积,求最多能装下的价值
每个物品可以拿ki次
https://www.acwing.com/problem/content/5/
一个优化:(二进制优化)
显然我们没有必要跑全ki次,判断下能用完全背包的就用完全背包好了
不能用完全背包的,考虑一个等价的次数,即,每次取1个,2个,4个。。。ki-2j+1个
j是最大的能使ki-2j+1>0的数
也就是说我们将ki二进制拆分了
时间复杂度为O(n*m*log(∑ki))
另一个优化:(单调队列优化)
————咕咕咕——————
时间复杂度O(n*m)
https://www.acwing.com/problem/content/6/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; int main(){ ll N,V,dp[20005] = {0}; scanf("%lld%lld",&N,&V); for(ll i=1,x,y,z;i<=N;i++){ scanf("%lld%d%lld",&x,&y,&z); if(x*z>V){ for(int j=x;j<=V;j++){ dp[j] = max(dp[j],dp[j-x]+y); } }else{ for(ll tmp = 1;z-tmp+1 > 0;tmp <<= 1){ ll k = (z-(tmp<<1)+1)<0?z-tmp+1:tmp; for(ll j=V;j>=x*k;j--){ dp[j] = max(dp[j],dp[j-x*k]+y*k); } } } } printf("%lld\n",dp[V]); return 0; }View Code
混合背包
前三个混在一起,加个if判断即可
https://www.acwing.com/problem/content/submission/7/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(a,b) (a>b?a:b) typedef long long ll; using namespace std; const int maxn = 2e4+7; int dp[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n--){ int k,value,cnt; scanf("%d%d%d",&k,&value,&cnt); if(cnt == -1){ for(int i=m;i>=k;i--){ dp[i] = max(dp[i],dp[i-k]+value); } }else if(cnt == 0 || k*cnt>=m){ for(int i=k;i<=m;i++){ dp[i] = max(dp[i],dp[i-k]+value); } }else{ for(int i=1;cnt-i+1>0;i<<=1){ int tmp = (cnt-(i<<1)+1)<0?cnt-i+1:i; for(int j=m;j>=tmp*k;j--){ dp[j] = max(dp[j],dp[j-tmp*k]+tmp*value); } } } } printf("%d\n", dp[m]); return 0; }View Code
二维费用的背包问题
物体不止有体积这个限制条件,还有质量这个限制条件
n个物体,v的背包容积,m的负重限制,还是01背包只能拿一个
https://www.acwing.com/problem/content/submission/8/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(a,b) (a>b?a:b) typedef long long ll; using namespace std; const int maxn = 1e3+7; int dp[maxn][maxn]; int main(){ int n,v,m; scanf("%d%d%d",&n,&v,&m); while(n--){ int volum,weight,value; scanf("%d%d%d",&volum,&weight,&value); for(int i=v;i>=volum;i--){ for(int j=m;j>=weight;j--){ dp[i][j] = max(dp[i][j],dp[i-volum][j-weight]+value); } } } printf("%d\n",dp[v][m]); return 0; }View Code
分组背包问题
每组只能拿一个,这样调整下for的顺序就好了
https://www.acwing.com/problem/content/submission/9/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(a,b) (a>b?a:b) typedef long long ll; using namespace std; const int maxn = 1e3+7; int dp[maxn]; int weight[maxn],value[maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n--){ int cnt; scanf("%d",&cnt); for(int i=1;i<=cnt;i++){ scanf("%d%d",&weight[i],&value[i]); } for(int i=m;i>=0;i--){ for(int j=1;j<=cnt;j++)if(i>=weight[j]){ dp[i] = max(dp[i],dp[i-weight[j]]+value[j]); } } } printf("%d\n",dp[m]); return 0; }View Code
有依赖的背包问题
要想拿当前物体,必须拿它的父亲
用dfs先处理处子节点,然后拿出当前节点(因为必须拿当前才能拿子节点)
做一个背包,然后把当前节点更新进去
https://www.acwing.com/problem/content/submission/10/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; const int maxn = 107; int n,m,root; int head[maxn],to[maxn],Next[maxn],tot = 1; int dp[maxn][maxn],val[maxn],wei[maxn]; void Add(int u,int v){ to[tot] = v; Next[tot] = head[u]; head[u] = tot++; } void dfs(int u){ for(int i=head[u];i;i=Next[i]){ int son = to[i]; dfs(son); for(int j=m-wei[u];j>=wei[son];j--){ for(int k=wei[son];k<=j;k++){ dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[son][k]); } } } for(int i=m;i>=wei[u];i--)dp[u][i] = dp[u][i-wei[u]]+val[u]; for(int i=0;i<wei[u];i++)dp[u][i] = 0; } int main(){ scanf("%d%d",&n,&m); for(int i=1,x;i<=n;i++){ scanf("%d%d%d",&wei[i],&val[i],&x); if(~x)Add(x,i); else root = i; } dfs(root); printf("%d\n",dp[root][m]); return 0; }View Code
背包问题求方案数
加一个数组,更新即可
https://www.acwing.com/problem/content/submission/11/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; const int maxn = 1e5+7,mod = 1e9+7; int n,m; int dp[maxn],ans[maxn]; int main(){ scanf("%d%d",&n,&m); fill(ans,ans+n,1); for(int i=1,x,y;i<=n;i++){ scanf("%d%d",&x,&y); for(int j=m;j>=x;j--){ if(dp[j]<dp[j-x]+y){ ans[j] = ans[j-x]; }else if(dp[j] == dp[j-x]+y){ ans[j] += ans[j-x]; ans[j] %= mod; } dp[j] = max(dp[j],dp[j-x]+y); } } printf("%d\n",ans[m]); return 0; }View Code
背包问题求具体方案
求字典序最小的方案
倒着来一遍背包,然后正着扫描一遍
https://www.acwing.com/problem/content/submission/12/
/*author:revolIA*/ #include<bits/stdc++.h> #define max(x,y) (x>y?x:y) using namespace std; typedef long long ll; const int maxn = 1e3+7,mod = 1e9+7; int n,m; int dp[maxn][maxn]; int x[maxn],y[maxn]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&x[i],&y[i]); } for(int i=n;i>=1;i--){ for(int j=0;j<x[i];j++) dp[i][j] = dp[i+1][j]; for(int j=x[i];j<=m;j++) dp[i][j] = max(dp[i+1][j],(dp[i+1][j-x[i]]+y[i])); } for(int i=1;i<=n;i++){ if(m>=x[i] && dp[i][m] == dp[i+1][m-x[i]]+y[i]){ printf("%d ",i); m -= x[i]; } } return 0; }View Code
原文链接:https://www.cnblogs.com/revolIA-room/p/11615797.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:长乐国庆集训Day4
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
- 用C++实现:完美的代价 2020-04-15
- 用C++实现:FJ的字符串打印 2020-04-04
- HDU-2955-Robberies(0-1背包) 2020-03-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash