2023年8月1日发(作者：)
[动态规划]背包问题（背包九讲+各种背包的模板题）01背包： 0代表不拿物品，1代表拿物品。每种物品⾄多只拿⼀件完全背包： 在01背包的基础上，每种物品可拿数量由⼀件变多件多重背包： 每种物品都有给定的数量,每种可拿物品不能超过本⾝固定的数量混合背包： 不⽌⼀种背包（01、完全、多重，其中的两种或三种）⼆维费⽤背包： 约束条件：背包重量限制，背包容量限制分组背包： 已经分好组的物品，然后按01背包取解决有依赖的背包： 背包添加物品时必须添加与其相依赖的物品背包问题求最优⽅案数： 最⼤总价值的⽅案数背包问题求具体⽅案： 最⼤总价值后按字典序获取具体⽅案（输出编号）---------01背包---------有n个重量和价值分别为wi，vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选⽅案中价值总和的最⼤值。如：n = 4，W = 5；物品编号重量 w[i]价值 v[i]i=023i=112i=234i=323⼆维数组实现：递推逐项求解：后⾯的状态等于前⾯的状态总和记dp[i+1][j]为从0到i这i+1的物品中挑选总重量不超过j的物品时的最⼤值；（保存最⼤价值）遍历j代表找出0~j重量范围内得到最⼤价值的总重量，为下⼀次dp做铺垫；如果j < w[i] 时，当前总重量区间不能选w[i]这件物品，所以dp不变，dp[i+1][j] = dp[i][j];如果j >= w[i] 时，当前总重量区间可以选w[i]这件物品，所以遍历找最⼤，dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);类⽐理解：我们可以把w=1，2，3，4，5当作五个容量不同的背包，0背包的状态肯定不存在，所以输出为0，每个背包在同⼀物品的状态都是不同的，背包状态可以分为⼀下四种：不含有物品的背包，其容量装下当前物品。不含有物品的背包，其容量可以装不下当前物品。已装有物品的背包，其剩下容量可以继续装下当前物品。已装有物品的背包，其剩下容量装不下当前物品。我们都知道了每个背包的状态是四种状态之⼀，但是我们不需要管他们，只了解⼀下就可以，因为背包容量本⾝就限制了⼤于背包容量的物品肯定装不下这个物品（其背包物品的总价值还是原来，dp[i][j]）。从这⾥我们知道背包容量，但是我们真正要考虑的是这个物品的价值是否值得装进背包（已装有物品的背包），所以我们就需要⽐较这个背包原来装⼊物品的总价值（原总价值dp[i][j]）与原装⼊物品和新装⼊物品的总价值（新总价值,dp[i][j-w[i]]+v[i]）,谁价值⼤就留下谁，得到d[i+1][j]。获取dp[i][j]的值：for(int i = 0;i < n;i++) for(int j = 0;j <= W;j++){ if(j>=w[i]) dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]); else dp[i+1][j] = dp[i][j]; }///dp[n][W]在这个递推式中，dp[i+1]只需计算dp[i+1]和dp[i],所以我们考虑⼀下滚动数组(奇偶性)，提⾼程序的效率：for(int i = 0;i < n;i++) for(int j = 0;j <= W;j++){ if(j>=w[i]) dp[(i+1)&1][j] = max(dp[i&1][j],dp[i&1][j-w[i]]+v[i]); else dp[(i+1)&1][j] = dp[i&1][j]; }///dp[n&1][W]，其他背包也可以⽤这种⽅法⼀维数组实现：⼆维数组把装物品的背包的总价值分为（n+1）*w种状态，它不需要更新状态，它把所有状态存下来了，⽽⼀维数组把装物品的背包的总价值分为w+1种状态，每装⼊⼀个物品都要更新⼀次dp。for(int i = 0;i < n;i++) for(int j = W;j >= w[i];j--) dp[j] = max(dp[j],dp[j-w[i]]+v[i]);///dp[w]---------完全背包---------有n种重量和价值分别为w[i],v[i]的物品。从这些物品中挑选总重量不超过W的物品，求处挑选物品价值总和的最⼤值。注意：每种物品可以挑选任意多件 。如：n = 3，W = 7；物品编号重量 w[i]价值 v[i]i=034i=145i=223⼆维数组实现，递推求法：存下所有的状态，还是(n+1)*w种状态。与01背包唯⼀不同的是在每个状态下还需要找出当前物品可以放多少个物品达到当前背包容量，并且价值最⼤ for(int i = 0;i < n; i++) for(int j = 0; j <= W; j++) for(int k = 0; k*w[i] <= j; k++) dp[i+1][j] = max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]); ///dp[n][w]///我们很容易明⽩其实枚举同种物品数量是多余了，k>=1部分已经在dp[i+1][j-w[i]]中实现///是不是还是⽆法明⽩这个多余计算包含在dp[i+1][j-w[i]]?下⾯再讲解for(int i = 0;i < n;i++) for(int j = 0;j <= W;j++){ if(j>=w[i]) dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]); else dp[i+1][j] = dp[i][j]; }///dp[n][W]⼀维数组实现：for(int i = 0;i < n;i++) for(int j = w[i];j <= W;j++) dp[j] = max(dp[j],dp[j-w[i]]+v[i]);///dp[w]从这⾥我们可以发现01背包的实现与完全背包的实现的差别只是循环顺序相反⽽已。我们如何理解：参考资料：状态转移⽅程：dp[j] = max(dp[j],dp[j-w[i]]+v[i]）W→w[i]： max中的dp[j]、dp[j-w[i]]是上⼀循环的状态。w[i]→W： max中的dp[j]、dp[j-w[i]]是本次循环的状态。我们可以发现dp[5] 为上⼀次循环的dp[5] 与这次循环的dp[5-2]⽐较，⽽dp[3]在这次循环中已经计算了，也就是说加了⼀次物品，⽽dp[5]这⾥再加⼀次，符合完全背包物品多件的性质。)---------多重背包---------有n种物品和⼀个容量为W的背包。第i种物品最多有num[i]件可⽤，每件费⽤是w[i]，价值是v[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。这⾥⼜多了⼀个限制条件，每个物品规定了可⽤的次数。朴素算法：for(int i = 0; i < n; i++) for(int j = 0;j < num[i]; j--) for(int k = W; k >= w[i]; k--) dp[k] = max(dp[k],dp[k-w[i]]+v[i]);⼆进制优化：我们都知道7的⼆进制为111，其可以分解为100、010、001三种⼆进制，这三个数组合成任意⼩于等于7的数，⽽每种组合都会得到不同的数。⽽我们可以把多重背包的⼀定数量的同种物品拆分为多种不同物品，从⽽就可以转化为01背包来求解了。///Value[]新物品的价值///size[]新物品的尺⼨///count新物品的个数，初始化为0for(int i = 0; i < n; i++){ for(int j = 1; j <= num[i]; j<<=1){///j=j*2 Value[count] = j * v[i]; size[count++] = j * w[i]; num[i]-=j } if(num[i]>0){///num[i]为偶数时，肯定最后有⼀个没有扫到 Value[count] = num[i] * v[i]; size[count++] = num[i] * w[i]; }}for(int i = 0; i < count; i++) for(int j = W; j >= size[i]; j--) dp[j] = max(dp[j],dp[j - size[i]]+Value[i]);单调队列优化：单调队列就是元素单调的队列。单调队列与普通队列不同的是单调队列可以从队⾸出队，也可以从队尾出队。先把物品分组,按（ 1,…,10）/w[i]的余数（余数为0~w[i]-1范围内）分组。如：w[i] = 3 W = 10时，3、6、9为⼀组，1、4、7、10为⼀组，2、5、8为⼀组。为什么要⽤dp[kw[i]+j] - kv[i] ？这个状态是之前的状态，⽽dp[k*w[i]+j] 为本次状态。（这⾥还是有点懵圈…请⼤佬们看到的话指点⼀下）///num[]物品固定数，相当于单调队列的滑动区间///p[]
存储⼊队元素的下标///k为商///j为余数for(int i = 1; i <= n; i++){ if(num[i]>W/w[i]) num[i] = W/w[i]; for(int j = 0; j< w[i]; j++){///j为W%w[i]的余数 int head = 1; int tail = 1; for(int k = 0; k*w[i]+j <= W; k++){ int temp = dp[k*w[i]+j] - k*v[i]; while(head
2023年8月1日发(作者：)
[动态规划]背包问题（背包九讲+各种背包的模板题）01背包： 0代表不拿物品，1代表拿物品。每种物品⾄多只拿⼀件完全背包： 在01背包的基础上，每种物品可拿数量由⼀件变多件多重背包： 每种物品都有给定的数量,每种可拿物品不能超过本⾝固定的数量混合背包： 不⽌⼀种背包（01、完全、多重，其中的两种或三种）⼆维费⽤背包： 约束条件：背包重量限制，背包容量限制分组背包： 已经分好组的物品，然后按01背包取解决有依赖的背包： 背包添加物品时必须添加与其相依赖的物品背包问题求最优⽅案数： 最⼤总价值的⽅案数背包问题求具体⽅案： 最⼤总价值后按字典序获取具体⽅案（输出编号）---------01背包---------有n个重量和价值分别为wi，vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选⽅案中价值总和的最⼤值。如：n = 4，W = 5；物品编号重量 w[i]价值 v[i]i=023i=112i=234i=323⼆维数组实现：递推逐项求解：后⾯的状态等于前⾯的状态总和记dp[i+1][j]为从0到i这i+1的物品中挑选总重量不超过j的物品时的最⼤值；（保存最⼤价值）遍历j代表找出0~j重量范围内得到最⼤价值的总重量，为下⼀次dp做铺垫；如果j < w[i] 时，当前总重量区间不能选w[i]这件物品，所以dp不变，dp[i+1][j] = dp[i][j];如果j >= w[i] 时，当前总重量区间可以选w[i]这件物品，所以遍历找最⼤，dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);类⽐理解：我们可以把w=1，2，3，4，5当作五个容量不同的背包，0背包的状态肯定不存在，所以输出为0，每个背包在同⼀物品的状态都是不同的，背包状态可以分为⼀下四种：不含有物品的背包，其容量装下当前物品。不含有物品的背包，其容量可以装不下当前物品。已装有物品的背包，其剩下容量可以继续装下当前物品。已装有物品的背包，其剩下容量装不下当前物品。我们都知道了每个背包的状态是四种状态之⼀，但是我们不需要管他们，只了解⼀下就可以，因为背包容量本⾝就限制了⼤于背包容量的物品肯定装不下这个物品（其背包物品的总价值还是原来，dp[i][j]）。从这⾥我们知道背包容量，但是我们真正要考虑的是这个物品的价值是否值得装进背包（已装有物品的背包），所以我们就需要⽐较这个背包原来装⼊物品的总价值（原总价值dp[i][j]）与原装⼊物品和新装⼊物品的总价值（新总价值,dp[i][j-w[i]]+v[i]）,谁价值⼤就留下谁，得到d[i+1][j]。获取dp[i][j]的值：for(int i = 0;i < n;i++) for(int j = 0;j <= W;j++){ if(j>=w[i]) dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]); else dp[i+1][j] = dp[i][j]; }///dp[n][W]在这个递推式中，dp[i+1]只需计算dp[i+1]和dp[i],所以我们考虑⼀下滚动数组(奇偶性)，提⾼程序的效率：for(int i = 0;i < n;i++) for(int j = 0;j <= W;j++){ if(j>=w[i]) dp[(i+1)&1][j] = max(dp[i&1][j],dp[i&1][j-w[i]]+v[i]); else dp[(i+1)&1][j] = dp[i&1][j]; }///dp[n&1][W]，其他背包也可以⽤这种⽅法⼀维数组实现：⼆维数组把装物品的背包的总价值分为（n+1）*w种状态，它不需要更新状态，它把所有状态存下来了，⽽⼀维数组把装物品的背包的总价值分为w+1种状态，每装⼊⼀个物品都要更新⼀次dp。for(int i = 0;i < n;i++) for(int j = W;j >= w[i];j--) dp[j] = max(dp[j],dp[j-w[i]]+v[i]);///dp[w]---------完全背包---------有n种重量和价值分别为w[i],v[i]的物品。从这些物品中挑选总重量不超过W的物品，求处挑选物品价值总和的最⼤值。注意：每种物品可以挑选任意多件 。如：n = 3，W = 7；物品编号重量 w[i]价值 v[i]i=034i=145i=223⼆维数组实现，递推求法：存下所有的状态，还是(n+1)*w种状态。与01背包唯⼀不同的是在每个状态下还需要找出当前物品可以放多少个物品达到当前背包容量，并且价值最⼤ for(int i = 0;i < n; i++) for(int j = 0; j <= W; j++) for(int k = 0; k*w[i] <= j; k++) dp[i+1][j] = max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]); ///dp[n][w]///我们很容易明⽩其实枚举同种物品数量是多余了，k>=1部分已经在dp[i+1][j-w[i]]中实现///是不是还是⽆法明⽩这个多余计算包含在dp[i+1][j-w[i]]?下⾯再讲解for(int i = 0;i < n;i++) for(int j = 0;j <= W;j++){ if(j>=w[i]) dp[i+1][j] = max(dp[i][j],dp[i+1][j-w[i]]+v[i]); else dp[i+1][j] = dp[i][j]; }///dp[n][W]⼀维数组实现：for(int i = 0;i < n;i++) for(int j = w[i];j <= W;j++) dp[j] = max(dp[j],dp[j-w[i]]+v[i]);///dp[w]从这⾥我们可以发现01背包的实现与完全背包的实现的差别只是循环顺序相反⽽已。我们如何理解：参考资料：状态转移⽅程：dp[j] = max(dp[j],dp[j-w[i]]+v[i]）W→w[i]： max中的dp[j]、dp[j-w[i]]是上⼀循环的状态。w[i]→W： max中的dp[j]、dp[j-w[i]]是本次循环的状态。我们可以发现dp[5] 为上⼀次循环的dp[5] 与这次循环的dp[5-2]⽐较，⽽dp[3]在这次循环中已经计算了，也就是说加了⼀次物品，⽽dp[5]这⾥再加⼀次，符合完全背包物品多件的性质。)---------多重背包---------有n种物品和⼀个容量为W的背包。第i种物品最多有num[i]件可⽤，每件费⽤是w[i]，价值是v[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。这⾥⼜多了⼀个限制条件，每个物品规定了可⽤的次数。朴素算法：for(int i = 0; i < n; i++) for(int j = 0;j < num[i]; j--) for(int k = W; k >= w[i]; k--) dp[k] = max(dp[k],dp[k-w[i]]+v[i]);⼆进制优化：我们都知道7的⼆进制为111，其可以分解为100、010、001三种⼆进制，这三个数组合成任意⼩于等于7的数，⽽每种组合都会得到不同的数。⽽我们可以把多重背包的⼀定数量的同种物品拆分为多种不同物品，从⽽就可以转化为01背包来求解了。///Value[]新物品的价值///size[]新物品的尺⼨///count新物品的个数，初始化为0for(int i = 0; i < n; i++){ for(int j = 1; j <= num[i]; j<<=1){///j=j*2 Value[count] = j * v[i]; size[count++] = j * w[i]; num[i]-=j } if(num[i]>0){///num[i]为偶数时，肯定最后有⼀个没有扫到 Value[count] = num[i] * v[i]; size[count++] = num[i] * w[i]; }}for(int i = 0; i < count; i++) for(int j = W; j >= size[i]; j--) dp[j] = max(dp[j],dp[j - size[i]]+Value[i]);单调队列优化：单调队列就是元素单调的队列。单调队列与普通队列不同的是单调队列可以从队⾸出队，也可以从队尾出队。先把物品分组,按（ 1,…,10）/w[i]的余数（余数为0~w[i]-1范围内）分组。如：w[i] = 3 W = 10时，3、6、9为⼀组，1、4、7、10为⼀组，2、5、8为⼀组。为什么要⽤dp[kw[i]+j] - kv[i] ？这个状态是之前的状态，⽽dp[k*w[i]+j] 为本次状态。（这⾥还是有点懵圈…请⼤佬们看到的话指点⼀下）///num[]物品固定数，相当于单调队列的滑动区间///p[]
存储⼊队元素的下标///k为商///j为余数for(int i = 1; i <= n; i++){ if(num[i]>W/w[i]) num[i] = W/w[i]; for(int j = 0; j< w[i]; j++){///j为W%w[i]的余数 int head = 1; int tail = 1; for(int k = 0; k*w[i]+j <= W; k++){ int temp = dp[k*w[i]+j] - k*v[i]; while(head
![[力扣]动态规划(DP)问题分类汇总](/uploads/image/0950.jpg)
发布评论