ps：dp全部初始化为0,指最大为j时的最大价值。 将dp初始化为-inf,dp[0] = 1,为容量为j的最大价值
01背包
#include<bits/stdc++.h> using namespace std; int dp[1001]; int v[1010],w[1010]; int main(){ int n , m; cin >> n >> m; dp[0][0] = 0; 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 ++ ) { //dp[i][j] = dp[i-1][j]; if(j >= v[i]) dp[j] = max(dp[j],dp[j-v[i]] + w[i]); } } // int res= 0; // for(int i = 0 ;i <= m ; i++) { // res = max(res , dp[n][i]); //} cout << f[m] << endl; return 0; }完全背包
#include<bits/stdc++.h> using namespace std; int dp[1001]; int v[1010],w[1010]; int main(){ int n , m; cin >> n >> m; // dp[0][0] = 0; 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 ++ ) { //dp[i][j] = dp[i-1][j]; if(j >= v[i]) dp[j] = max(dp[j],dp[j-v[i]] + w[i]); } } int res= 0; for(int i = 0 ;i <= m ; i++) { res = max(res , dp[i]); } cout << res << endl; return 0; }多重背包（只能解决数据范围小的）
#include<bits/stdc++.h> using namespace std; int dp[1001]; int v[1010],w[1010],u[1010]; int main(){ int n , m; cin >> n >> m; // dp[0][0] = 0; for(int i = 1; i <= n ; i ++){ cin >> v[i] >> w[i] >> u[i]; } for(int i = 1; i <= n ; i++){ for(int j = m; j >= 0 ; j -- ) { /// for(int k = 0; k <= u[i] && k * v[i] <= j ; k++) //dp[i][j] = dp[i-1][j]; if(j >= v[i]) dp[j] = max(dp[j],dp[j-k * v[i]] + k * w[i]); } } cout << dp[m] << endl; return 0; }多组背包2（二进制优化）
#include<bits/stdc++.h> using namespace std; const int maxn = 2010; int dp[maxn]; int v,w,u; struct node{ int u , v; }np; vector<node> ve; int main(){ int n , m ; cin >> n >> m; for(int i = 1 ; i <= n ;i ++){ cin >> v >> w >> u; for(int k = 1; k <= u ; k *= 2){ u -= k; ve.push_back({k * v , k * w}); } if(m > 0) ve.push_back({u * v , u * w}); } for(auto nps : ve){ for(int i = m ; i >= nps.u; i --){ dp[i] = max(dp[i],dp[i-nps.u] + nps.v); } } cout << dp[m] << endl; return 0 ; }多组背包究极版（滑稽）3*1e8硬是让我卡过去了
#include<bits/stdc++.h> using namespace std; //手动扩栈 #pragma comment(linker,"/STACK:102400000,102400000") //~victor~Alexander 20:03:51 #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") %:pragma GCC optimize("-fgcse") %:pragma GCC optimize("-fgcse-lm") %:pragma GCC optimize("-fipa-sra") %:pragma GCC optimize("-ftree-pre") %:pragma GCC optimize("-ftree-vrp") %:pragma GCC optimize("-fpeephole2") %:pragma GCC optimize("-ffast-math") %:pragma GCC optimize("-fsched-spec") %:pragma GCC optimize("unroll-loops") %:pragma GCC optimize("-falign-jumps") %:pragma GCC optimize("-falign-loops") %:pragma GCC optimize("-falign-labels") %:pragma GCC optimize("-fdevirtualize") %:pragma GCC optimize("-fcaller-saves") %:pragma GCC optimize("-fcrossjumping") %:pragma GCC optimize("-fthread-jumps") %:pragma GCC optimize("-funroll-loops") %:pragma GCC optimize("-fwhole-program") %:pragma GCC optimize("-freorder-blocks") %:pragma GCC optimize("-fschedule-insns") %:pragma GCC optimize("inline-functions") %:pragma GCC optimize("-ftree-tail-merge") %:pragma GCC optimize("-fschedule-insns2") %:pragma GCC optimize("-fstrict-aliasing") %:pragma GCC optimize("-fstrict-overflow") %:pragma GCC optimize("-falign-functions") %:pragma GCC optimize("-fcse-skip-blocks") %:pragma GCC optimize("-fcse-follow-jumps") %:pragma GCC optimize("-fsched-interblock") %:pragma GCC optimize("-fpartial-inlining") %:pragma GCC optimize("no-stack-protector") %:pragma GCC optimize("-freorder-functions") %:pragma GCC optimize("-findirect-inlining") %:pragma GCC optimize("-fhoist-adjacent-loads") %:pragma GCC optimize("-frerun-cse-after-loop") %:pragma GCC optimize("inline-small-functions") %:pragma GCC optimize("-finline-small-functions") %:pragma GCC optimize("-ftree-switch-conversion") %:pragma GCC optimize("-foptimize-sibling-calls") %:pragma GCC optimize("-fexpensive-optimizations") %:pragma GCC optimize("-funsafe-loop-optimizations") %:pragma GCC optimize("inline-functions-called-once") %:pragma GCC optimize("-fdelete-null-pointer-checks") const int maxn = 20010; int dp[maxn]; int v,w,u; struct node{ int u , v; }np; vector<node> ve; int main(){ int n , m ; ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 1 ; i <= n ;i ++){ cin >> v >> w >> u; for(int k = 1; k <= u ; k *= 2){ u -= k; ve.push_back({k * v , k * w}); } if(m > 0) ve.push_back({u * v , u * w}); } for(auto nps : ve){ for(int i = m ; i >= nps.u; i --){ dp[i] = max(dp[i],dp[i-nps.u] + nps.v); } } cout << dp[m] << endl; return 0 ; }真正的究极版（单调队列 + 滚动数组）
混合背包问题 （转换成01和完全解决）
#include<bits/stdc++.h> using namespace std; const int maxn = 1010; struct node{ int kind; int v ,w; }; int n , m ; int v , w , k; int dp[maxn]; int main(){ cin >> n >> m; vector<node> ve; for(int i = 1; i <= n ; i++){ cin >> v >> w >> k; if(k < 0) ve.push_back({-1,v,w}); else if(k == 0) ve.push_back({0,v,w}); else { for(int j = 1; j <= k ; j ++){ k -= j ; ve.push_back({-1,j * v ,j * w }); } if(k > 0) ve.push_back({-1,k * v , k * w}); } } for(auto np : ve){ if(np.kind == -1) { for(int j = m ; j >= np.v; j --){ dp[j] = max(dp[j], dp[j -np.v ] + np.w); } } else { for(int j =np.v ; j <= m; j++){ dp[j] = max(dp[j] , dp[j - np.v] + np.w); } } } cout << dp[m] << endl; return 0 ; }二维费用的背包问题
#include<bits/stdc++.h> using namespace std; //int u[1010],s[1010],w[1010]; int dp[1010][1010]; int main(){ int n , v , m ; cin >> n >> v >> m; for(int i = 1; i <= n ; i++){ int u , s , w; cin >> u >> s >> w; for(int j = v ; j >= u ; j --){ for(int k = m ; k >= s; k--){ dp[j][k] = max(dp[j][k] , dp[j - u][k - s] + w); } } } cout << dp[v][m] << endl; return 0; }分组背包问题
#include<bits/stdc++.h> using namespace std; //vector<int> a[110]; int x[110],y[110]; int dp[110]; int main(){ int n,m; cin >> n >> m; for(int i = 1; i <= n ; i++){ int t; cin >> t; // int x,w; for(int k = 1 ; k <= t; k ++) cin >> x[k] >> y[k]; for(int j = m;j >=0; j -- ){ for(int k = 1 ; k <= t; k ++) if(j >= x[k]) dp[j] = max(dp[j],dp[j -x[k] ] + y[k]); } } cout << dp[m] << endl; return 0; }有依赖的背包问题
#include <bits/stdc++.h> using namespace std; const int maxn = 1010; struct edge{ int to , nxt , w, v; }e[maxn << 1]; int n,m ; int dp[maxn][maxn]; int v[maxn], w[maxn]; int tot; int head[maxn]; void add_edge(int u , int v){ // v // e[tot].w = w; // e[tot].v = x; e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot ++; } void dfs(int u){ for(int i = head[u]; ~i ; i = e[i].nxt){ int y = e[i].to; dfs(y); for(int j = m - v[u];j >= 0; j--){ for(int k = 0; k <= j ; k ++){ dp[u][j] = max(dp[u][j] , dp[u][j - k] + dp[y][k]); } } } //cout << v[u] << endl; for(int i = m; i >= v[u] ; i--){ dp[u][i] = dp[u][i - v[u]] + w[u]; } for(int i = 0 ; i < v[u];i ++){ dp[u][i] = 0; } } int main(){ memset(head,-1,sizeof head); cin >> n >> m; int root; for(int i = 1; i <= n ; i++){ //v , w ,p int p; cin >> v[i] >> w[i] >> p; if(p == -1) root = i; else add_edge(p,i); } dfs(root); cout << dp[root][m] << endl; return 0; }背包问题求方案数
#include <bits/stdc++.h> using namespace std; const int maxn = 1010,mod = 1e9 + 7; int n , m; int v[maxn],w[maxn]; int dp[maxn],cnt[maxn]; const int inf = 9999999; int main(){ cin >> n >> m; cnt[0] = 1; for(int i = 1; i <= m ; i++) dp[i] = -inf; for(int i = 0; i < n ; i++){ int v, w; cin >> v >> w; int s = 0; for(int j = m ; j >= v; j --){ s = 0; int t = max(dp[j] ,dp[j - v] + w); if(t == dp[j]) s += cnt[j]; if(t == dp[j - v] + w ) s+= cnt[j - v]; if(s >= mod) s-= mod; dp[j] = t; cnt[j] = s; } } int maxx = 0; for(int i = 0 ;i <= m ; i++) maxx = max(maxx,dp[i]); int res = 0; for(int i = 0 ; i <= m ; i++){ if(maxx == dp[i]) {res += cnt[i]; if(res >= mod) res -= mod; } } cout << res << endl; return 0; }背包问题求具体方案
#include <bits/stdc++.h> using namespace std; const int maxn = 1010,mod = 1e9 + 7; int n , m; int v[maxn],w[maxn]; int dp[maxn][maxn],cnt[maxn]; const int inf = 9999999; int main(int argc, char const *argv[]) { cin >> n >> m; for(int i = 1; i <= n ; i++) cin >> v[i] >> w[i]; for(int i = n ; i >= 1; i--) for(int j = 0; j <= m ; j++){ dp[i][j] = dp[i+1][j]; if(j >= v[i]) dp[i][j] = max(dp[i][j] ,dp[i+1][j - v[i]] + w[i]); } int val = m; for(int i =1; i <= n ; i++){ if(dp[i][val] == dp[i+1][val - v[i]] + w[i] && val-v[i]>=0){ //vol-v[i]>=0 cout << i << ' ' ; val -= v[i]; } } return 0; }