01背包：
#include <iostream> 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]; if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]); } } cout << f[n][m] << endl; return 0; } #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; int v[1010],w[1010]; int dp[1010]; int n,m; int main() { std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i<n;i++) cin>>v[i]>>w[i]; for(int i=0;i<n;i++) for(int j=m;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } cout<<dp[m]; return 0; }完全背包：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; int v[1010],w[1010]; int dp[1010]; int n,m; int main() { std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=0;i<n;i++) cin>>v[i]>>w[i]; for(int i=0;i<n;i++) for(int j=v[i];j<=m;j++) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); cout<<dp[m]; return 0; }多重背包1：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n,m; int v[1010],w[1010],dp[1010][1010],s[1010]; int main() { std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); 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=m;j>=0;j--){ for(int k=0;k<=s[i];k++) { if(j>=k*v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]); } } cout<<dp[n][m]; return 0; } #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n,m; int f[1010][1010]; int v[1010],w[1010],s[1010]; int main() { std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); 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=m;j>=0;j--) for(int k=0;k<=s[i]&&k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k) cout<<f[n][m]; return 0; }一维版本：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=110; int v[N],w[N],s[N]; int dp[N]; int main() { int n, m; 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 = m; j >= v[i] ; j--) { for(int k = 0; k <= s[i] && k * v[i] <= j; k ++) { dp[j] = max(dp[j], dp[j- k * v[i]] + k * w[i]); } } } cout << dp[m] << endl; return 0; }多重转01：
#include <bits/stdc++.h> using namespace std; int a[10005],b[10005]; int main() { int t=0,n,m,dp[10005]={ },w,v,s; cin>>n>>m; while(n--) { cin>>v>>w>>s; while(s--) {a[++t]=v; b[t]=w;}//死拆，把多重背包拆成01背包 } for(int i=1;i<=t;i++) for(int j=m;j>=a[i];j--) dp[j]=max(dp[j-a[i]]+b[i],dp[j]);//直接套01背包的板子 cout<<dp[m]<<endl; return 0; }多重背包二进制优化版本
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=12010,M=2010; int n,m; int v[N],w[N]; int f[M]; int main() { std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0); 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++;//二进制能凑出s以下的所有数 v[cnt]=a*k; w[cnt]=b*k; s-=k; k*=2; } if(s>0){ cnt++; v[cnt]=a*s; w[cnt]=b*s; } } n=cnt; for(int i=1;i<=n;i++)//01背包 for(int j=m;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); cout<<f[m]; return 0; }分组背包:
#include<iostream> #include<algorithm> #include<set> #include<queue> #include<vector> using namespace std; const int N=110; int n,m; int v[N][N],w[N][N],s[N]; int f[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 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(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); cout<<f[m]; return 0; }