动态规划-背包问题专题

动态规划-背包问题及其变形长沙市一中曹毅回顾：动态规划的核心要素基本概念：1.阶段2.状态3.状态转移方程使用条件：1.最优子结构2.无后效性背包问题：01背包问题完全背包问题多重背包问题混合背包问题二维费用的背包问题分组背包问题有依赖背包问题01背包有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路：对于第i件物品，我们有两个选择：放或者不放，用f[i][v]表示前i件物品恰放入容量为v的最大价值，于是有两种情况：1.不放：f[i][v]=f[i-1][v]2.放：f[i][v]=f[i-1][v-c[i]]+w[i]最后取这两者的最大值于是得出状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}边界：f[1][0]=0（不装任何东西）核心代码：fori=1..nforv=v..0f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}时空分析及优化以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。f[i][v]-f[v]‘f[v]表示重量不超过V公斤的最大价值数据：104重量价值求得：21334579f[1]0f[2]1f[3]3f[4]5f[5]5f[6]6f[7]9f[8]9f[9]10f[10]12完全背包问题有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。区别：第i件物品可以无限装，01背包只能装一次转换：f[v]=max{f[v],f[v-k*w[i]]+k*c[i]}其中0=k*w[i]=vfori=1..nforv=0..vf[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}01背包与完全背包对比数据：104重量价值求得：2133457901背包f[1]0f[2]1f[3]3f[4]5f[5]5f[6]6f[7]9f[8]9f[9]10f[10]12完全背包f[1]0f[2]1f[3]3f[4]5f[5]5f[6]6f[7]9f[8]10f[9]10f[10]12完全背包的优化：1.简单优化：w[i]=w[j]且c[i]=c[j]则去掉j物品（性价比低）2.二进制优化，核心思想：将第i种物品拆成若干个物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+10的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。目的还是转换为01背包问题。多重背包问题：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。分析：类似完全背包，k的取值范围有所变化f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0=k=n[i]}。复杂度是O(V*∑n[i])混合背包问题：其实是将多种背包问题混在一起，无需多讲，在循环时根据不同的背包类型进行不同的处理即可，此处不再赘述。二维费用背包问题：同上，加多一维数组即可。状态转移方程：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}分组背包问题（同组互斥）有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。分析：这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于第k组}。（以组为单位进行枚举）分组背包问题（同组互斥）使用一维数组的伪代码如下：for所有的组kforv=V..0for所有的i属于组kf[v]=max{f[v],f[v-c[i]]+w[i]}有依赖背包问题（同组依赖）这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。于是抽象会形成一颗树！！（树形DP）解决方案：1.每个主件里的物品可选可不选，于是在主件内部又存在一个01背包问题。2.将主件内物品进行一次01背包，于是主件间的关系形成了类似分组背包问题，即可用分组背包解决。更高级的东西泛化问题求最优方案总数建议认真阅读“背包九讲”这篇神东西。