关于背包问题的总结
2022/2/10 23:14:57
本文主要是介绍关于背包问题的总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
背包问题的分类:
1. 01背包问题
2. 完全背包问题
3. 多重背包问题
4. 完全背包问题
DP问题的解题思路:
- 01背包问题
问题描述:见例题:01背包问题
问题分析:对于每一个物品,可以选择要也可以选择。所以状态的计算就是更新i所表示的集合,因此,f(i,j) = max(f[i-1][j],f[i-1][j-v[i]]+w[i])。这就是朴素版的01背包问题,代码如下:
#include<bits/stdc++.h> using namespace std; const int N = 1010; int n,m; int v[N],w[N]; int f[N][N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } for(int i=1;i<=n;i++) { for(int j = 0;j<=m;j++) { f[i][j] = f[i-1][j];//不选第i个物品 if(v[i] <= j) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]); //看看选了第i个是否更好 } } cout<<f[n][m]<<endl; return 0; }
优化:我们可以发现i状态的f只与i-1有关,因此可以用滚动数组进行优化,只用一个一维数组就可以保存答案。此时j循环需要从m到v[i],因为j-v[i]的状态要在j状态更新之后。代码如下:
#include<bits/stdc++.h> using namespace std; const int N = 1010; int n,m; int v[N],w[N]; int f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v[i]>>w[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]); } } cout<<f[m]<<endl; return 0; }
2.完全背包问题 完全背包问题
问题分析:对于每一个物品,可以不选择,也可以选择任意多个(所选体积需要小于V)
朴素版代码如下:(会超时)
#include<bits/stdc++.h> using namespace std; const int N = 1010; int v[N],w[N]; int n,m; int f[N][N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v[i]>>w[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]); } } } cout<<f[n][m]<<"\n"; return 0; }
优化如下:
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]+k*w)
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-kv]+(k-1)w)
第一个在第二个式子上面加上一个w。
所以f[i][j]可以优化为max(f[i][j],f[i][j-v]+w);
代码如下:
#include<bits/stdc++.h> using namespace std; const int N = 1010; int v[N],w[N]; int n,m; int f[N][N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } 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]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]); } } cout<<f[n][m]<<"\n"; return 0; }
最后按照上面的更新方法,根据滚动数组,优化为一维的。
因为这里的状态更新是根据本层来更新的,所以不需要逆序。
#include<bits/stdc++.h> using namespace std; const int N = 1010; int v[N],w[N]; int n,m; int f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v[i]>>w[i]; } for(int i=1;i<=n;i++) { for(int j=v[i];j<=m;j++) { f[j] = max(f[j],f[j-v[i]]+w[i]); } } cout<<f[m]<<"\n"; return 0; }
3.多重背包问题 多重背包I
问题分析,这里合完全背包区别在于数量不是无限的,因此,稍加修改即可
#include<bits/stdc++.h> using namespace std; const int N = 110; int n,m; int v[N],w[N],s[N]; int f[N][N]; 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++) { 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]); } } } cout<<f[n][m]<<endl; return 0; }
多重背包优化 多重背包问题II
这里使用二进制来进行优化,每一种物品都可以用1,2,4,8…捆绑表示,所以可以将此问题转化为01背包问题,物品是捆绑之后的物品。这里直接写最后代码:
#include<bits/stdc++.h> using namespace std; const int N = 1010,M = 25000; int n,m; int v[M],w[M]; int f[M]; int main() { cin>>n>>m; int cnt = 0;//计算捆绑的编号 for(int i = 1;i<=n;i++) { int a,b,s; cin>>a>>b>>s; int k = 1; while(k <= s) { cnt++; v[cnt] = k*a; w[cnt] = k*b; s -= k; k*=2; } if(s) {cnt++;v[cnt] = s*a,w[cnt] = s*b;} } n=cnt; 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]); } } cout<<f[m]<<endl; return 0; }
4.分组背包问题:分组背包
朴素版:
#include<bits/stdc++.h> using namespace std; const int N = 110; int n,m; int v[N][N],w[N][N],s[N]; int f[N][N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>s[i]; for(int j=0;j<s[i];j++) { cin>>v[i][j]>>w[i][j]; } } for(int i=1;i<=n;i++) { for(int j =0;j<=m;j++) { f[i][j] = f[i-1][j]; for(int k=0;k<s[i];k++) { if(v[i][k] <= j) f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); } } } cout<<f[n][m]<<endl; return 0; }
按照刚刚的方法进行优化
#include<bits/stdc++.h> using namespace std; const int N = 110; int n,m; int v[N][N],w[N][N],s[N]; int f[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>s[i]; for(int j=0;j<s[i];j++) { cin>>v[i][j]>>w[i][j]; } } for(int i=1;i<=n;i++) { for(int j =m;j>=0;j--) { for(int k=0;k<s[i];k++) { if(v[i][k] <= j) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]); } } } cout<<f[m]<<endl; return 0; }
背包问题到此结束
参考 : ACWing基础课
这篇关于关于背包问题的总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南