背包问题
01背包
二维:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef long long ll; const int N=1e3+5; int n,m,v[N],w[N],f[N][N]; int main() { cin.tie(0),cout.tie(0); 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=1;j<=m;++j){ if(j<v[i])f[i][j]=f[i-1][j]; else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); } } cout<<f[n][m]; return 0; }View Code
一维:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef long long ll; const int N=1e3+5; int n,m,v[N],w[N],f[N]; int main() { cin.tie(0),cout.tie(0); 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]; return 0; }View Code
完全背包
二维:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef long long ll; const int N=1e3+5; int n,m,v[N],w[N],f[N][N]; int main() { cin.tie(0),cout.tie(0); 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){ if(j<v[i])f[i][j]=f[i-1][j]; else f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]); } } cout<<f[n][m]; return 0; }View Code
一维:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef long long ll; const int N=1e3+5; int n,m,v[N],w[N],f[N]; int main() { cin.tie(0),cout.tie(0); 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]; return 0; }View Code
多重背包
分组背包
标签:typedef,背包,int,cin,long,tie,动态,规划 From: https://www.cnblogs.com/bible-/p/17097013.html