内网网站建设所需硬件设备,白云怎样优化网站建设,建设银行个人登录网站,化工类 网站模板目录
01背包#xff1a;
完全背包#xff1a;
多重背包#xff08;范围0-100#xff09;#xff1a;
混合背包#xff1a;
分组背包#xff1a;
二维费用的背包问题#xff1a;
背包问题求方案数#xff1a; 01背包#xff1a;
从最大容量开始遍历到当前
完全背包
多重背包范围0-100
混合背包
分组背包
二维费用的背包问题
背包问题求方案数 01背包
从最大容量开始遍历到当前防止重复
void solve()
{int n,m,v,w;cinnm;for(int i1;in;i){cinvw;for(int jm;jv;j--){dp[j]max(dp[j],dp[j-v]w);}}coutdp[m]endl;return ;
}
完全背包
从当前容量遍历到最大与01背包恰好相反
void solve()
{int n,m,v,w;cinnm;for(int i1;in;i){cinvw;for(int jv;jm;j){dp[j]max(dp[j],dp[j-v]w);}}coutdp[m]endl;return ;
}
多重背包范围0-100
范围小的时候适用将有数量都转为1转化为01背包
void solve()
{int n,m,v[101001],w[101001],ans1,a,b,c;cinnm;for(int i1;in;i){cinabc;for(int j1;jc;j){v[ans]a;w[ans]b;ans;}}for(int i1;ians;i){for(int jm;jv[i];j--){dp[j]max(dp[j],dp[j-v[i]]w[i]);}}coutdp[m]endl;return ;
}
混合背包
void solve()
{int n,m;cinnm;for (int i1;in;i) {int v,w,s;cinvws;if(s0)//当完全背包做{for(int jv;jm;j) dp[j] max(dp[j],dp[j-v]w);}else //转化为01背包{if(s-1)s1;for(int k1;ks;k1){for(int jm;jv*k;j--){dp[j]max(dp[j],dp[j-v*k]w*k);}s-k;}if(s){for(int jm;js*v;j--){dp[j]max(dp[j],dp[j-v*s]w*s); }}}}coutdp[m]endl; return ;
}
分组背包
signed main()
{int n,m,s,w[1010],v[1010];cinnm;while(n--){cins;for(int i1;is;i)cinv[i]w[i];for(int jm;j0;j--){for(int k1;ks;k){if(jv[k])dp[j]max(dp[j],dp[j-v[k]]w[k]);}}}coutdp[m]endl;return 0;
}
二维费用的背包问题
除体积限制外多了质量限制
void solve()
{int n,v,m;cinnvm;for (int i1;in;i) {int a,b,w;cinabw;for(int jv;ja;j--){for(int km;kb;k--){dp[j][k]max(dp[j][k],dp[j-a][k-b]w);}}}coutdp[v][m]endl; return ;
}
背包问题求方案数
signed main()
{int n,m,v,w;cinnm;for(int i0;im;i)cnt[i]1;for(int i1;in;i){cinvw;for(int jm;jv;j--){int tdp[j-v]w;if(tdp[j]){dp[j]t;cnt[j]cnt[j-v];}else if(tdp[j]){cnt[j](cnt[j]cnt[j-v])%mod;}}}coutcnt[m]endl;return 0;
}
今日推荐音乐我想我不够好 迷失幻境
下一篇子数组的解释与专题
