背包九讲（C++）

目录背包问题1.0/1背包2.完全背包3.多重背包4.分组背包5.混合背包问题6.背包问题求具体方案7.背包问题求方案数8.二维费用的背包问题9.有依赖的背包问题背包问题任何背包问题都有01背包的影子甚至均可以化为01背包的问题(特殊性)而任何背包都是多重背包的特殊情况01背包和完全背包分别是多重背包分组个数的极端情况即多重背包具有普遍性可以说只要理解了多重背包其它的背包问题也就跟着解决了我也会通过代码注释的形式帮助读者理解这句话1.0/1背包​//朴素版代码 // #include iostream // using namespace std; // const int N1e39; // int dp[105][N]; // int n,m; // int main() // { // cinnm; // dp[0][0]0; // for(int i1;in;i) // { // int w,v;cinwv; // for(int j0;jm;j) // { // //不选 // dp[i][j]dp[i-1][j]; // //选 // if(jw) // dp[i][j]max(dp[i][j],dp[i-1][j-w]v); // } // } // coutdp[n][m]; // return 0; // } //优化代码 #include iostream using namespace std; const int N1e39; int dp[N]; int n,m; int main() { cinnm; for(int i1;in;i) { int w,v;cinwv; for(int jm;jw;j--) dp[j]max(dp[j],dp[j-w]v);////不选时dp[i][j]dp[i-1][j] } coutdp[m]; return 0; }2.完全背包当空间优化成一维之后只有完全背包问题的体积是从小到大循环的​//朴素版代码 // #include iostream // using namespace std; // const int N1e310; // int dp[N][N]; // int main() // { // int n,m;cinnm; // for(int i1;in;i) // { // int w,v;cinwv; // for(int j0;jm;j) // { // //第i类物品不选 // dp[i][j]dp[i-1][j]; // //第i类物品选 // for(int k1;k*wj;k) // { // dp[i][j]max(dp[i][j],dp[i-1][j-k*w]k*v);//第i类物品可以选多次取最大的一次 // } // } // } // coutdp[n][m]\n; // return 0; // } //优化代码: //因为dp[i][j]max(dp[i-1][j],dp[i-1][j-w]v,dp[i-1][j-2*w]2*v……dp[i-1][j-k*w]k*v……) // dp[i][j-w]vmax(dp[i-1][j-w]v,dp[i-1][j-2*w]2*v,……dp[i-1][j-k*w]k*v……) //所以: dp[i][j]max(dp[i-1][j],dp[i][j-w]v) //也说明了j需要从小到大循环这是与0/1背包最大的不同j需要当前第i层循环的j-w来更新 #includeiostream using namespace std; const int N1e39; int dp[N]; int main() { int n,m;cinnm; for(int i1;in;i) { int w,v;cinwv; for(int jw;jm;j) { dp[j]max(dp[j],dp[j-w]v);//不选时dp[i][j]dp[i-1][j] } } coutdp[m]; }3.多重背包根据数据规模选择合适的优化方法10^2/s : 化为01背包10^3/s : 二进制优化将一个一个遍历变为一群一群遍历10^4/s : 单调队列优化求滑动窗口内的最大值​//朴素版代码 // #include iostream // using namespace std; // const int N103,M203; // int f[N][M]; // int n,m; // int main() // { // cinnm; // for(int i1;in;i) // { // int v,w,s;cinvws; // for(int j0;jm;j) // { // f[i][j]f[i-1][j]; // for(int k1;ks;k) // { // if(jk*v) // f[i][j]max(f[i][j],f[i-1][j-k*v]k*w); // } // } // } // coutf[n][m]\n; // return 0; // } //优化版本 //思路一:化为01背包 //时间复杂度O(n*m*s) #include iostream using namespace std; const int N103,M203; int f[M]; int n,m; int main() { cinnm; for(int i1;in;i) { int v,w,s;cinvws; ////多重背包化为01背包把每种物品的s件一一摊开视为s个相同属性的物品即化为01背包 while(s--)////对每个物品循环s[i]次其余同01背包 for(int jm;jv;j--) { f[j]max(f[j],f[j-v]w); } } coutf[m]\n; return 0; } //思路二二进制优化 //时间复杂度O(n*m*log s) #includeiostream using namespace std; const int N2005; int f[N]; int n,m; int vv[20],ww[20]; int main() { cinnm; for(int i1;in;i) { int s,v,w;cinvws; int cnt0; for(int k1;ks;k1) {//有二进制优化的方法将原来思考一的一个一个地枚举变为一群一群地枚举 vv[cnt]v*k; ww[cnt]w*k; s-k; } if(s) { vv[cnt]v*s;//将这一群的物品看成一个物品 ww[cnt]w*s; } for(int k1;kcnt;k) { for(int jm;jvv[k];j--) f[j]max(f[j],f[j-vv[k]]ww[k]); } } coutf[m]\n; return 0; } //思路三滑动窗口单调队列 //时间复杂度O(n*m) #include iostream #includecstring using namespace std; const int N103,M203; int f[M],g[M],q[M]; int n,m; int main() { cinnm; for(int i1;in;i) { int v,w,s;cinvws; memcpy(g,f,sizeof f);//存一下上一层的元素 for(int j0;jv;j) { int hh1,tt0; for(int kj;km;kv) { if(hhtt(k-q[hh])/vs) hh;//如果窗口大于s个单位,则窗口前移 while(hhttg[q[tt]]-(q[tt]-j)/v*wg[k]-(k-j)/v*w) tt--;//运用单调队列优化求滑动窗口中的最值 q[tt]k;//入队队列存贮的是体积大小hh、tt只是q数组下标用于模拟队列和控制滑动窗口 if(hhtt) f[k]max(f[k],g[q[hh]](k-q[hh])/v*w);//窗口内的最大值进行状态转移 } } } coutf[m]\n; return 0; }4.分组背包分组背包组内的每一种选择均互斥这是与多重背包的本质区别​#includeiostream using namespace std; const int N110; int f[N],v[N],w[N]; int n,m,s; int main() { cinnm; for(int i1;in;i) { cins; for(int j1;js;j) cinv[j]w[j]; for(int jm;j0;j--) for(int k1;ks;k) if(jv[k]) f[j]max(f[j],f[j-v[k]]w[k]);//对于同i组的物品分别考虑每一物品的选与不选这里与01背包很像 } coutf[m]\n; }5.混合背包问题这题能非常清晰地看出01背包、完全背包、多重背包的关联。​#includeiostream using namespace std; const int M1005; int f[M]; int vv[M],ww[M]; int n,m; int main() { cinnm; for(int i1;in;i) { int v,w,s;cinvws; if(s0) { for(int jv;jm;j)//完全背包 f[j]max(f[j],f[j-v]w); } else { if(s-1) s1;//01背包是多重背包s1时的特殊情况 int cnt0; for(int k1;ks;k1)//二进制优化的多重背包 { vv[cnt]v*k; ww[cnt]w*k; s-k; } if(s) { vv[cnt]v*s; ww[cnt]w*s; } for(int k1;kcnt;k) { for(int jm;jvv[k];j--) f[j]max(f[j],f[j-vv[k]]ww[k]); } } } coutf[m]\n; return 0; }6.背包问题求具体方案​#includeiostream using namespace std; const int N1005; int f[N][N]; int n,m; int v[N],w[N]; int main() { cinnm; for(int i1;in;i) cinv[i]w[i]; for(int in;i1;i--)//f[i][j]表示从i到n的选择情况 { for(int j0;jm;j) { f[i][j]f[i1][j]; if(jv[i]) f[i][j]max(f[i][j],f[i1][j-v[i]]w[i]); } } int jm; for(int i1;in;i)//因为最后一件物品存储的是最终状态所以从最后一件物品进行循环 {//我们不能正着寻找答案因为从0到1我们对于最优解中的第一件物品不知道选的是第几个物品从而无法确定他的初始体积多少但反着来我们一定会知道它的最后体积必为m if(jv[i]f[i][j]f[i1][j-v[i]]w[i]) { couti ; j-v[i]; } } return 0; }7.背包问题求方案数​//思路一体积恰好为i #includeiostream #includecstring using namespace std; const int N1005,mod1e97; int f[N],g[N];//f[i]表示体积恰好为i的最优解g[i]表示最优解的方案数 int n,m; int main() { cinnm; memset(f,-0x3f,sizeof f); //从这个状态表示我们就该想到它与普通01背包的区别了我们需要在开始将所有的f都初始化为负无穷 //那么不能使体积恰好为j的情况就会被淘汰指不会被递推过去 g[0]1; f[0]0; for(int i1;in;i) { int v,w;cinvw; for(int jm;jv;j--) { int maxvmax(f[j],f[j-v]w); int cnt0; if(maxvf[j]) cntg[j]; if(maxvf[j-v]w) cntg[j-v]; g[j]cnt%mod; f[j]maxv; } } int res0; for(int i0;im;i) resmax(res,f[i]); int ans0; for(int i0;im;i) { if(resf[i]) ans(ansg[i])%mod; } coutans\n; return 0; } //思路二体积不超过i #includeiostream using namespace std; const int N1005; const int mod1e97; int f[N],g[N];////f[i]表示体积不超过i的最优解g[i]表示最优解的方案数 int n,m; int main() { cinnm; for(int i0;im;i) g[i]1;//不论是哪个体积下总有一个对应的最大价值方案数为1 for(int i1;in;i) { int v,w;cinvw; for(int jm;jv;j--) { if(f[j-v]wf[j]) { f[j]f[j-v]w; g[j]g[j-v];//一条路 } else if(f[j-v]wf[j]) g[j](g[j]g[j-v])%mod;//两条路 } } coutg[m]\n;//体积不超过m的最大价值方案数 return 0; }8.二维费用的背包问题理解二维费用的背包问题代码中的多重循环能更好地理解背包问题中循环递推的过程。​//f[i,j]表示总体积和总重量分别不超过i,j的最优解这与单个物品的体积和重量毫不相关就不是同一个概念 //因此多重循环并没有割裂单个物品的体积和重量 #includeiostream using namespace std; const int N105; int f[N][N]; int n,V,M; int main() { cinnVM; for(int i1;in;i) { int v,m,w;cinvmw; for(int jV;jv;j--) { for(int kM;km;k--) { f[j][k]max(f[j][k],f[j-v][k-m]w); } } } coutf[V][M]\n; return 0; }9.有依赖的背包问题​#includeiostream #includecstring //树形DP分组背包 using namespace std; const int N105; int e[N],ne[N],h[N],idx; int v[N],w[N]; int n,m; int f[N][N]; //a是b的父节点 void add(int a,int b) {//用数组模拟邻接表用于存储图效率比STL中的容器高 e[idx]b,ne[idx]h[a],h[a]idx; //idx:数组模拟的下标(指针)即表示该元素在数组中的位置每存储一个元素就用偏移一次 //e[idx]:数组模拟的实际值用于存储结点号 //ne[idx]:e[idx]的下一个结点 //h[]:表示头结点初始时头结点指向-1也就是相当与多个链表的头结点放在了一个数组中 }//这个操作相当于在链表的头结点和头结点指向的元素之间插入一个结点插入结点的顺序对图没有影响 void dfs(int u) { for(int ih[u];~i;ine[i])//循环物品组 { int sone[i]; dfs(son); //分组背包 for(int jm-v[u];j0;j--)//循环物品 { for(int k0;kj;k)//循环决策按体积进行决策 f[u][j]max(f[u][j],f[u][j-k]f[son][k]); } } //将u加进去 for(int im;iv[u];i--) f[u][i]f[u][i-v[u]]w[u]; for(int i0;iv[u];i) f[u][i]0;//体积不够那以u为根的树的体积为0 } int main() { cinnm; memset(h,-1,sizeof h);//头结点的初始化指向-1表示无儿子 int root1; for(int i1;in;i) { int p; cinv[i]w[i]p; if(p-1) rooti; else add(p,i); } dfs(root); coutf[root][m]\n; return 0; }