#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N][N], v[N], w[N];intmain(){
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 -1][j - v[i]]+ w[i]);}}
cout << f[n][m]<< endl;return0;}
01背包-2
#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N], g[N], v[N], w[N];intmain(){
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])
g[j]= f[j];else
g[j]=max(f[j], f[j - v[i]]+ w[i]);}memcpy(f, g,sizeof g);}
cout << f[m]<< endl;return0;}
01背包-3
#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N], v[N], w[N];intmain(){
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;return0;}
完全背包
完全背包-1
#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N][N], v[N], w[N];intmain(){
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]<< endl;return0;}
完全背包-2
#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N], v[N], w[N];intmain(){
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]<< endl;return0;}
完全背包-2(恰好装满m)
#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N], v[N], w[N];intmain(){
cin >> n >> m;for(int i =1; i <= n;++i)
cin >> v[i]>> w[i];memset(f,128,sizeof f);// 初始化为负无限大
f[0]=0;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]<< endl;return0;}
多重背包
多重背包-1 (n <= 100)
#include<bits/stdc++.h>usingnamespace std;constint N =1e5+10;int n, m, f[N], v[N], w[N], l[N];intmain(){
cin >> n >> m;for(int i =1; i <= n;++i)
cin >> v[i]>> w[i]>> l[i];for(int i =1; i <= n;++i){for(int k =1; k <= l[i];++k){for(int j = m; j >= v[i];--j){
f[j]=max(f[j], f[j - v[i]]+ w[i]);}}}
cout << f[m]<< endl;return0;}