前言：
DP一直是博主的一大心头痛啊，真的完全小白状态，最近刷完了至少20道的背包问题，在这篇博客中我将会将我认为有启发价值的题目列出来，中间会有筛选的（质量保证）。在复习例题前，我会先将背包的几种基本状态做个总结。请务必知道所有类型的背包后再来阅读。
一.简单背包类型总结
1.01背包
for(int i=1;i<=n;i++) for(in j=W;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
2.完全背包
for(int i=1;i<=n;i++) for(int j=w[i];j<=W;j++) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
3.多重背包
1)暴力拆分( O( W*sum(c[i]) ) )
for(int i=1;i<=n;i++) for(int k=1;k<=c[i];k++) for(int j=W;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
2）二进制拆分( O( W*sum ( log(c[i]) ) ) )
cin>>n; for(int i=1;i<=n;i++) { cin>>cw>>cv>>c; int now=1; while(now<=c) { w[++cnt].s=cw*now; v[cnt].s=cv*now; w[cnt].id=i; v[cnt].id=i; c-=now; now*=2; } if(c) { w[++cnt].s=cw*c; w[cnt].id=i; v[cnt].id=i; v[cnt].s=cv*c; } } cin>>m; n=cnt; for(int i=1;i<=n;i++) for(in j=W;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
3)数组优化（O（n*W））
for(int i=1;i<=n;i++) { memset(num,0,sizeof(num)); for(int j=w[i];j<=W;j++) { if(dp[j]<dp[j-w[i]] && num[j-w[i]]<c[i]) { dp[j]=dp[j-w[i]]+v[i]; num[j]=num[j-w[i]]+1; } } }
PS：这个中间一直memset，可以换了，感觉常数有点大。
4.分组背包
for(int i=1;i<=n;i++) for(int j=W;j>=0;j--) for(int k=1;k<=c[i];k++) { if(j>=w[i][k]) { dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]); } }
5.混合背包
PS:混合背包有多种类型的组合，但原理相通。考虑到哪个物品时，就按这个物品的模式去递推一层即可。所以这里没有给出具体代码。
二.简单例题
1.1417烹饪方案
我们发现因为时间的缘故导致物品的顺序对结果会有影响，所以我们先决定选的顺序。手推一下就可以发现按某种规律排列再去一个个选会有最优结果。然后就是个01DP，这里注意了因为t会对答案有影响且会有负数的存在所以中途要一直取max才行。
#include<bits/stdc++.h> #define ll long long using namespace std; struct node { ll a,b,c; bool operator < (const node &tt) const { return -tt.b*c>-b*tt.c; } }a[1001]; ll dp[1000010],t,n; int main() { ll ans=0; cin>>t>>n; for(int i=1;i<=n;i++) cin>>a[i].a; for(int i=1;i<=n;i++) cin>>a[i].b; for(int i=1;i<=n;i++) cin>>a[i].c; sort(a+1,a+1+n); for(int i=1;i<=n;i++) for(int j=t;j>=a[i].c;j--) { dp[j]=max(dp[j],dp[j-a[i].c]+a[i].a-j*a[i].b); ans=max(ans,dp[j]); } cout<<ans; return 0; }
2.1855
这个题倒不是多难，就是放这提一下二维背包dp
#include<bits/stdc++.h> using namespace std; const int maxn=1000; int n,m,t; int mm[maxn],tt[maxn]; int dp[maxn][maxn]; int main() { cin>>n>>m>>t; for(int i=1;i<=n;i++) cin>>mm[i]>>tt[i]; for(int i=1;i<=n;i++) for(int M=m;M>=mm[i];M--) for(int T=t;T>=tt[i];T--) dp[M][T]=max(dp[M-mm[i]][T-tt[i]]+1,dp[M][T]); cout<<dp[m][t]; return 0; }
3.5020货币系统
这个题倒也不是多难，就是这个数学证明，我不会证明，但我看完题目就看出了正解（并非凡尔赛），最后答案就是这个系统中有几个数字能被系统中其他数字组合出来。
4.金明的预算方案
呃....有了附件，各种乱七八糟的关系，这就很烦了。但因为附件最多只有2个，所以我们对于每个主件可以有
1.只选主件
2.一个都不选
3.选主件和附件一
4.选主件和附件二
5.都选
然后就是个01背包
5.2946
这个算我见过的简单dp中有点特殊的,dp[i][j]表示考虑选了i头奶牛时，前i个组成的和modf=j的组合数。然后就是01背包。
#include<bits/stdc++.h> using namespace std; const int p=1e8; int n,f; int r[100010]; long long h[2010][1010]; int main() { cin>>n>>f; for(int i=1;i<=n;i++) { cin>>r[i]; r[i]%=f; } for(int i=1;i<=n;i++) h[i][r[i]]=1; for(int i=1;i<=n;i++) for(int j=0;j<f;j++) h[i][j]=((h[i][j]+h[i-1][j])%p+h[i-1][(j-r[i]+f)%f])%p; cout<<h[n][0]; return 0; }
6.1156垃圾陷阱
呃就是dp[t][h]表示时间为t秒时，高度为h时，剩余的最大生命值。
这个题我才用的时从0开始往后推的一种dp形式，也算dp的一种技巧。
然后在dp的过程中，判断是否能逃出去。如果一轮dp下来仍然每逃出去，则必死无疑，重新求答案，这就是个简单模拟，就是不停的吃。
#include<bits/stdc++.h> using namespace std; int dp[101][101]; struct node { int t,f,h; bool operator < (const node &a) const { return t<a.t; } }r[100010]; int d,g; int main() { memset(dp,-1,sizeof(dp)); cin>>d>>g; for(int i=1;i<=g;i++) cin>>r[i].t>>r[i].f>>r[i].h; sort(r+1,r+1+g); dp[0][0]=10; for(int i=0;i<g;i++) for(int j=0;j<=d;j++) { if(dp[i][j]<0) continue ; if(j+r[i+1].h>=d && dp[i][j]-r[i+1].t+r[i].t>=0) { cout<<r[i+1].t<<endl; return 0; } if(dp[i][j]-r[i+1].t+r[i].t>=0) { dp[i+1][j+r[i+1].h]=max(dp[i+1][j+r[i+1].h],dp[i][j]-r[i+1].t+r[i].t); } if(dp[i][j]-r[i+1].t+r[i].t>=0) dp[i+1][j]=max(dp[i+1][j],dp[i][j]-r[i+1].t+r[i].t+r[i+1].f); } int m=10,sum=0; for(int i=1;i<=g;i++) { if(r[i].t-r[i-1].t>m) { cout<<m+sum; return 0; } sum+=(r[i].t-r[i-1].t); m-=(r[i].t-r[i-1].t); m+=r[i].f; } cout<<sum+m; return 0; }
7.5322排兵布阵
这个题题解都在说什么排序啊什么的，我表示听不懂，就是个分组背包嘛，我就拍了几分钟，一次AC。（不是在凡尔赛）但是常数好像有点大吧？.....
#include<bits/stdc++.h> using namespace std; int s,n,m,x; int dp[1000001]; int c[10001][10001],t[1001][40010],sum[10000][10000]; struct { int w,v; }ttt[1010][1010]; int pp[100010]; int main() { cin>>s>>n>>m; for(int i=1;i<=s;i++) { for(int j=1;j<=n;j++) { cin>>x; c[j][i]=x; t[j][x*2+1]++; pp[j]=max(pp[j],x*2+1); } } for(int i=1;i<=n;i++) { for(int j=1;j<=pp[i]+2;j++) { sum[i][j]=sum[i][j-1]+t[i][j]*i; } } for(int i=1;i<=n;i++) for(int j=1;j<=s;j++) { ttt[i][j].w=c[i][j]*2+1; ttt[i][j].v=sum[i][c[i][j]*2+1]; } for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=s;k++) { if(j>=ttt[i][k].w) { dp[j]=max(dp[j],dp[j-ttt[i][k].w]+ttt[i][k].v); } } cout<<dp[m]; return 0; }
8.4138挂饰
每个挂件有4种可能：
1.有挂钩，价值为正（取它）
2.无挂钩，价值为负（打死都不取）
3.有挂钩，价值为负（考虑ing...）
4.无挂钩，价值为正（考虑ing....）
如何考虑呢，第三种情况就用01背包滚一遍，第四种情况就先排序，再和第三种情况解出的dp数组组合一下答案，取最大值。
详见代码：
#include<bits/stdc++.h> using namespace std; const int maxn=2010; int x,y,cnt,cnt1; int b[maxn]; bool cmp(const int A,const int B) { return A>B; } int ans_1,ans_2,s[maxn]; int f[maxn]; struct { int x,v; }a[maxn]; int main() { int n; ans_1=1; cin>>n; for(int i=1;i<=n;i++) { cin>>x>>y; if(x==0) { if(y<=0) continue ; else b[++cnt]=y; } else { if(y>=0) ans_1+=x-1,ans_2+=y; else a[++cnt1].x=x-1,a[cnt1].v=y; } } ans_1=min(ans_1,n); for(int i=0;i<=2000;i++) f[i]=-999999999; for(int i=0;i<=ans_1;i++)f[i]=0; for(int i=1;i<=cnt1;i++) for(int j=2000;j>=a[i].x;j--) f[j]=max(f[j],f[j-a[i].x]+a[i].v); sort(b+1,b+1+cnt,cmp); for(int i=1;i<=2000;i++) s[i]=s[i-1]+b[i]; int ans=0; for(int i=0;i<=2000;i++) { ans=max(ans,f[i]+s[i]); } cout<<ans+ans_2; return 0; }
9.2340
呃，容量时n,价值为智商，体积为情商（可以交换），然后dp[j]就表示当前情商和为j时最大的智商和，因为j可能是个负数，所以整体将数组右移即可，然后就是背包滚一遍，最后统计答案。因为有负数，所以要从头到尾统计一遍。
#include<bits/stdc++.h> using namespace std; const int maxn=1001; const int maxm=401; struct { int iq,eq; }a[8000000]; int cnt=0; int n,x,y; int dp[8000000]; int ans_s,ans_f,ans; int main() { cin>>n; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; if(x<=0 && y<=0) continue ; if(x>=0 && y>=0) ans_s+=x,ans_f+=y; else { a[++cnt].iq=x; a[cnt].eq=y; } } memset(dp,-0X3F,sizeof(dp)); dp[400000]=0; for(int i=1;i<=n;i++) { if(a[i].iq>=0) { for(int j=800000;j>=a[i].iq;j--) dp[j]=max(dp[j],dp[j-a[i].iq]+a[i].eq); } else { for(int j=0;j<=800000+a[i].iq;j++) dp[j]=max(dp[j],dp[j-a[i].iq]+a[i].eq); } } int ans=-999; for(int i=400000;i<=800000;i++) if(dp[i]>0) ans=max(ans,i+dp[i]-400000); ans+=ans_f+ans_s; if(ans<0) cout<<0; else cout<<ans; return 0; }
10.4095
因为原来是有顺序的从前往后，所以删除一个就会对整个dp数组有影响，那么我们就前缀后缀各滚一遍，用二维dp来存。
#include<bits/stdc++.h> using namespace std; int n,cw,cv,c,m; int cnt; long long f1[100010][1010]; long long f2[100010][1010]; struct { int s,id; }w[1000010],v[1000010]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>cw>>cv>>c; int now=1; while(now<=c) { w[++cnt].s=cw*now; v[cnt].s=cv*now; w[cnt].id=i; v[cnt].id=i; c-=now; now*=2; } if(c) { w[++cnt].s=cw*c; w[cnt].id=i; v[cnt].id=i; v[cnt].s=cv*c; } } cin>>m; n=cnt; for(int i=1;i<=n;i++) { for(int j=0;j<=1000;j++) f1[i][j]=f1[i-1][j]; for(int j=1000;j>=w[i].s;j--) f1[i][j]=max(f1[i][j],f1[i-1][j-w[i].s]+v[i].s); } for(int i=n;i>=1;i--) { for(int j=0;j<=1000;j++) f2[i][j]=f2[i+1][j]; for(int j=1000;j>=w[i].s;j--) f2[i][j]=max(f2[i][j],f2[i+1][j-w[i].s]+v[i].s); } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; x++; long long ans=0; int l=0; while(w[l+1].id<x && l<n) l++; int r=l; while(w[r+1].id<=x && r<n) r++; for(int j=0;j<=y;j++) { ans=max(ans,f1[l][j]+f2[r+1][y-j]); } cout<<ans<<endl; } return 0; }
复习的也差不多了
可以再去试试：（就是不想写）
1.纪念品（CSP2019PJ）（懒得讲）
2.emiya的饭（CSP2019TG）（准备留到容斥再讲）
3.皮配（十二省联考）（太难）
总结：
背包问题最精髓就在于，有“体积”，有“价值”，选或不选......然后就是分析题意，是什么类型的背包DP,这就看选择物品的个数限制了，或者分组背包（多选一）。（DP纯靠感觉qwq）