01背包：
从最大容量开始遍历到当前，防止重复
void solve() { int n,m,v,w; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v>>w; for(int j=m;j>=v;j--) { dp[j]=max(dp[j],dp[j-v]+w); } } cout<<dp[m]<<endl; return ; }
完全背包：
从当前容量遍历到最大，与01背包恰好相反
void solve() { int n,m,v,w; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>v>>w; for(int j=v;j<=m;j++) { dp[j]=max(dp[j],dp[j-v]+w); } } cout<<dp[m]<<endl; return ; }
多重背包（范围0-100）：
范围小的时候适用，将有数量都转为1，转化为01背包
void solve() { int n,m,v[101001],w[101001],ans=1,a,b,c; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a>>b>>c; for(int j=1;j<=c;j++) { v[ans]=a; w[ans]=b; ans++; } } for(int i=1;i<=ans;i++) { for(int j=m;j>=v[i];j--) { dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } cout<<dp[m]<<endl; return ; }
混合背包：
void solve() { int n,m; cin>>n>>m; for (int i=1;i<=n;i++) { int v,w,s; cin>>v>>w>>s; if(s==0)//当完全背包做 { for(int j=v;j<=m;j++) dp[j] = max(dp[j],dp[j-v]+w); } else //转化为01背包 { if(s==-1) s=1; for(int k=1;k<=s;k<<=1) { for(int j=m;j>=v*k;j--) { dp[j]=max(dp[j],dp[j-v*k]+w*k); } s-=k; } if(s) { for(int j=m;j>=s*v;j--) { dp[j]=max(dp[j],dp[j-v*s]+w*s); } } } } cout<<dp[m]<<endl; return ; }
分组背包：
signed main() { int n,m,s,w[1010],v[1010]; cin>>n>>m; while(n--) { cin>>s; for(int i=1;i<=s;i++) cin>>v[i]>>w[i]; for(int j=m;j>=0;j--) { for(int k=1;k<=s;k++) { if(j>=v[k]) dp[j]=max(dp[j],dp[j-v[k]]+w[k]); } } } cout<<dp[m]<<endl; return 0; }
二维费用的背包问题：
除体积限制外多了质量限制
void solve() { int n,v,m; cin>>n>>v>>m; for (int i=1;i<=n;i++) { int a,b,w; cin>>a>>b>>w; for(int j=v;j>=a;j--) { for(int k=m;k>=b;k--) { dp[j][k]=max(dp[j][k],dp[j-a][k-b]+w); } } } cout<<dp[v][m]<<endl; return ; }
背包问题求方案数：
signed main() { int n,m,v,w; cin>>n>>m; for(int i=0;i<=m;i++) cnt[i]=1; for(int i=1;i<=n;i++) { cin>>v>>w; for(int j=m;j>=v;j--) { int t=dp[j-v]+w; if(t>dp[j]) { dp[j]=t; cnt[j]=cnt[j-v]; } else if(t==dp[j]) { cnt[j]=(cnt[j]+cnt[j-v])%mod; } } } cout<<cnt[m]<<endl; return 0; }
