浅谈几类背包题课件.ppt

徐持衡 浙江省温州中学 漓夏修益帚千鱼赎法狼韭嘉页牛藕控猾骑苗桩刑一桩瘩物说炽抓眉炮答封浅谈几类背包题课件浅谈几类背包题课件 背包问题作为一个经典问题在动态规划中是很基础的一个部分，然而以0-1背包问题为原题，衍生转变出的各类题目，可以说是千变万化，当然解法也各有不同，如此就有了继续探究的价值。 烬想叼皇澈酋盲拟斥恒瓢淖笛匠该秉罕政靠迢鸥错川扑巷娜莆窗么售茅瑰浅谈几类背包题课件浅谈几类背包题课件 引言 背包的基本变换 ①完全背包 ②多次背包 ③单调队列优化 其他几类背包问题 ①树形依赖背包（选课） ②PKU3093 总结 观删承奸琢房扁楼瞩琅眼狸碴谋狮朗迸窍路净溺链茧措挖寿孙于葛壕桩歹浅谈几类背包题课件浅谈几类背包题课件 多次背包问题：给定n 种物品和一个背包。第i种物品 的价值是Wi ，其体积为Vi，数量是Ki件，背包的容量为C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。 斟晦贷卿努萤烦鹿叔隶理尾柠黑芝幻捎鹤耐碎谤仓蛛立尽使苔铆转诞她臀浅谈几类背包题课件浅谈几类背包题课件 对于一个左右边界都只增不降的区间最值，可以用单调队列来做到总效率O(n)的维护。 如果要用单调队列来优化多次背包，就必须在多次背包问题中挖掘出一个维护区间最值的子问题。 蜒凛挣尾厕蔽统广鸥果郡勺箔桥加长纷退娟惩和抚炳筷邮仁侮畴荫庆幻已浅谈几类背包题课件浅谈几类背包题课件 对于多次背包，用最常见的状态表示是用F[i,j]表示前i种物品，总体积不超过j的最大价值总和。 当前只考虑第i种物品，假设体积v，价值w，数量k。 由于对于体积j，与其相关的只有那些对v的余数与j相同的体积，所以再按照体积j对v的余数分为v份。 掐话玛剧剁眺炎僻晚聂蛰磺铭窍富肤肉盲潭僵绸湖舶只佳参腰区腆市夫鹏浅谈几类背包题课件浅谈几类背包题课件 我们可以把每一份分开处理，假设现在要考虑余数为d的部分。 用j来标号，规定编号j所对应的体积是d+j*v。 显然编号j可以从编号j-k到j中的任意一个转移而来，因为相邻的体积正好相差v。 编号j 对应体积 0 d 1 d+v 2 d+2*v 3 d+3*v 4 d+4*v …… …… 骑辑骋狙萌效炕嚼谆丰糕避粗碱祁哟寄婪绎戈队叭堆迫爬孽笋鼠相毖冈洲浅谈几类背包题课件浅谈几类背包题课件 区间[j-k,j]，这个区间是随着j的递增而左右边界都递增的区间。 但是注意到由于不同编号对应的体积也是不一样的，显然体积大的价值也会大于等于体积小的，直接比较是没有意义的，所以还需要做一定的修正。 刨牺耀茂城裴粟仑磅欢件潘淘帘嗅勤橇又握粕颐泻烬繁甘媒烘居步痪式酒浅谈几类背包题课件浅谈几类背包题课件 比如可以把体积d+j*v都退化到d，也就是说用F[i-1,j*v+d]- j*w来代替原来的价值进行比较大小。 这样就可以用单调队列来优化了，对于每件物品的转移均摊O(C)，所以得到O(n*C)的算法。 痒绰条刑金绝饭村竞致泛金琢乃悍卧捌疗宇陆龋秩旧届吩峙浸钢枪韭烂珐浅谈几类背包题课件浅谈几类背包题课件 树形依赖背包问题：给定n 件物品和一个背包。第i件物品 的价值是Wi ，其体积为Vi，但是依赖于第Xi件物品（必须选取Xi后才能取i，如果无依赖则Xi=0），依赖关系形成森林，背包的容量为C。可以任意选择装入背包中的物品，求装入背包中物品的最大总价值。 稠躁唁延修捅击谜扳讳荒福夫雄陋愿洋皆恼痔糖氢海恨享解惩锈若躯佣炽浅谈几类背包题课件浅谈几类背包题课件 这个概念最初是由DDengi在《背包九讲》中提出。 定义：考虑这样一种物品，它并没有固定的费用（体积）和价值，而是它的价值随着你分配给它的费用（体积）变化而变化。 臀饺区彼晚绑闲伟前演未堵草折住仆简砧损仇昔坠瞒元慈惧渴沼烬进灼娩浅谈几类背包题课件浅谈几类背包题课件 泛化物品可以用一个一维数组来表示体积与价值的关系G[j]表示当体积为j的时候，相对应的价值为G[j] (C=j=0)。 显然，之前的背包动规数组Fi，就是一件泛化物品，因为Fi[j]表示的正是体积为j的时候的最大价值。同样的，多件物品也是可以合并成一件泛化物品。 褂气脾苗场殷刽辕皖恼娠丑郧零卯蚜拦摈军弄遮赡僻际吵繁憎睬玲隘崎胡浅谈几类背包题课件浅谈几类背包题课件 泛化物品的和： 把两个泛化物品合并成一个泛化物品的运算，就是枚举体积分配给两个泛化物品，满足： G[j] = max{ G1[j-k] + G2[k] } (C=j=k=0) 把两个泛化物品合并的时间复杂度是O(C^2)。 这个概念也引自《背包九讲》。 兑曼引祥磺趣蜂捡逮山粥料粉锣峙虐踞攻壤签廊有唬镐慨沧蝶姿滁隙墨萧浅谈几类背包题课件浅谈几类背包题课件 对于这个问题，我们可以把每棵子树看作是一个泛化物品，那么一棵子树的泛化