资源描述：
《动态规划-背包问题专题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划-背包问题及其变形长沙市一中曹毅回顾：动态规划的核心要素基本概念：阶段状态状态转移方程使用条件：最优子结构无后效性背包问题：01背包问题完全背包问题多重背包问题混合背包问题二维费用的背包问题分组背包问题有依赖背包问题01背包有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路：对于第i件物品，我们有两个选择：放或者不放，用f[i][v]表示前i件物品恰放入容量为v的最大价值，于是有两种情况：
2、不放：f[i][v]=f[i-1][v]放：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)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化
3、到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[
4、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]
5、<=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+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。目的还是转换为01背包问题。多重背包问题：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i
6、]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。分析：类似完全背包，k的取值范围有所变化f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]
7、0<=k<=n[i]}。复杂度是O(V*∑n[i])混合背包问题：其实是将多种背包问题混在一起，无需多讲，在循环时根据不同的背包类型进行不同的处理即可，此处不再赘述。二维费用背包问题：同上，加多一维数组即可。状态转移方程：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i
8、]][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]
9、物品i属于第
10、k组}。（以组为单位进行枚举）分组背包问题（同组互斥）使用一维数组的伪代码如下：for所有的组kforv=V..0for所有的i属于组kf[v]=max{f[v],f[v-c[i]]+w[i]}有依赖背包问题（同组依赖）这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。将不
