背包问题（模板）

目录

01背包：

完全背包：

多重背包（范围0-100）：

混合背包：

分组背包：

二维费用的背包问题：

背包问题求方案数：

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;
}

今日推荐音乐：我想我不够好  迷失幻境

下一篇：子数组的解释与专题