动态规划-背包问题专题ppt课件.ppt

《动态规划-背包问题专题ppt课件.ppt》由会员分享，可在线阅读，更多相关《动态规划-背包问题专题ppt课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能动态规划动态规划 -背包问题及其变形背包问题及其变形长沙市一中长沙市一中 曹毅曹毅为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能回顾：动态规划的核心要素回顾：动态规划的核心要素q基本概念：1.1.阶段阶段2.2.状态状态3.3.状态转移方程状态转移方程q使用条件：1.1.最优最优子结构子结构2.2.无后效性无后效性为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能

2、背包问题：背包问题：q01背包问题 q完全背包问题 q多重背包问题 q混合背包问题 q二维费用的背包问题 q分组背包问题 q有依赖背包问题 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能0101背包背包q有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。q基本思路：对于第i件物品，我们有两个选择：放或者不放，用fiv表示前i件物品恰放入容量为v的最大价值，于是有两种情况：1.1.不不放：放：fiv=fi-1v fiv=fi-1v 2.2.

3、放：放：fiv=fi-1v-ci+wifiv=fi-1v-ci+wi最后取这两者的最大值最后取这两者的最大值为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能于是得出状态转移方程：于是得出状态转移方程：qfiv=maxfi-1v,fi-1v-ci+wiq边界：f10=0（不装任何东西）q核心代码：for i=1.n for v=v.0 fiv=maxfi-1v,fi-1v-wi+ci为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能时空分析及优化时空分析及优化q以上方法的时间

4、和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。qfiv-fv fv表示重量不超过V公斤的最大价值q数据：10 4重量 价值 求得：2 13 34 57 9f1 0f2 1f3 3f4 5f5 5f6 6f7 9f8 9f9 10f10 12为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能完全背包问题完全背包问题q有N种物品和一个容量为V的背包，每种物品都有无无限限件件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最

5、大。q区别：第i件物品可以无限装，01背包只能装一次转换：fv=maxfv,fv-k*wi+k*ci 其中0=k*wi=vfor i=1.n for v=0.v fiv=maxfi-1v,fi-1v-wi+ci为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能0101背包与完全背包对比背包与完全背包对比q数据：10 4重量 价值 求得：2 1 3 3 4 5 7 901背包f1 0f2 1f3 3f4 5f5 5f6 6f7 9f8 9f9 10f10 12完全背包f1 0f2 1f3 3f4 5f5 5f6 6f7 9f8 10f9

6、 10f10 12为什么？为什么？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能完全背包的优化：完全背包的优化：q1.简单优化：wi=cj则去掉j物品（性价比低）q2.二进制优化，核心思想：将第i种物品拆成若干个物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,.,2(k-1),ni-2k+1，且k是满足ni-2k+10的最大整数。例如，如果ni为13，就将这种物品分成系数分别为1,2,4,6的四件物品。目的还是转换为01背包问题。为深入学习习近平新时代中国特色社会主

7、义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能多重背包问题：多重背包问题：q有N种物品和一个容量为V的背包。第i种物品最多有ni件可用，每件费用是ci，价值是wi。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。q分析：类似完全背包，k的取值范围有所变化qfiv=maxfi-1v-k*ci+k*wi|0=k=ni。复杂度是O(V*ni)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能混合背包问题：混合背包问题：q其实是将多种背包问题混在一起，无需多讲，在循环时根据不同的背包类型

8、进行不同的处理即可，此处不再赘述。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二维费用背包问题：二维费用背包问题：q同上，加多一维数组即可。q状态转移方程：fivu=maxfi-1vu,fi-1v-aiu-bi+wi fivu=maxfi-1vu,fi-1v-aiu-bi+wi为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能分组背包问题（同组互斥）分组背包问题（同组互斥）q有N件物品和一个容量为V的背包。第i件物品的费用是ci，价值是wi。这些物品被划分为若干组，每组

9、中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。q分析：这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设fkv表示前k组物品花费费用v能取得的最大 权 值，则 有 fkv=maxfk-1v,fk-1v-ci+wi|物品i属于第k组。（以组为单位进行枚举）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能分组背包问题（同组互斥）分组背包问题（同组互斥）q使用一维数组的伪代码如下：for 所有的组k for v=V.0 for 所有的i属于组k f

10、v=maxfv,fv-ci+wi为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能有依赖背包问题（同组依赖）有依赖背包问题（同组依赖）q这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。q将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。于是抽象会形成一颗树！（树形DP）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能解决方案：解决方案：q1.每个主件里的物品可选可不选，于是在主件内部又存在一个01背包问题。q2.将主件内物品进行一次01背包，于是主件间的关系形成了类似分组背包问题，即可用分组背包解决。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能更高级的东西更高级的东西q泛化问题q求最优方案总数q建议认真阅读“背包九讲”这篇神东西。