算法合集之《浅谈数据的合理组织》（精品）.ppt

谢　谢 四川省绵阳南山中学　 何森 浅谈数据的合理组织 引子 题目越来越难——数据关系越来越复杂！ 对组织数据的要求越来越高！ 合理组织在解题中越来越重要！ 【题意描述】 给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，一个主件最多有两个附件，附件没有下一级附件。 【任务】 用不超过M元钱，购买一些物品，使得被购买的物品的总权值最大。 金明的预算方案 【数据规模】 N60　 M3200 题目中给出的主件与附件间形成树形结构，而所有的物品间形成森林结构。为了方便起见，我们给所有的主件都加上一个“上级主件”，这样，所有的物品形成了一棵树。 数据的初步组织 树形动态规划算法! 算法1 状态F[i][j]表示给以i为根的子树，总共花费不超过j元，所能取得的最大权值和。 ? ? ? 枚举量太大，效率不高！ 总花费不超过j 用左儿子右兄弟表示法来表示这一棵树！ 时间复杂度为 O(NM2) 状态总数 O(MN) 状态转移代价 O(M) N*M*M=6*108　，不太理想。 状态F[i][j]表示以i为根的子树总共花费j元能获得的最大权值和。 我们只需要枚举给左子树分配多少钱，剩下的钱都分给右子树。 我们把配套的主件和附件看成一组。 这样，显然对于每一组，可能的购买方案最多只有如下五种： 我们换一种数据组织方式 1.　附件没有附件。 2.　每个主件最多只有两个附件。 考虑本题特殊条件： 1.什么都不买 2.只购买主件 3.购买主件和附件1 4.购买主件和附件2 5.全购买 类似经典的０-１背包问题！ 组织数据后，我们可以得到复杂度为O(NM)的优秀算法 状态总数 O(MN) 状态转移代价 O(1) 郁闷的金明 【题意描述】 给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，主件可以有任意多附件，附件没有下一级附件。 【任务】 用不超过M元钱，购买一些物品，使得被购买的物品的总权值最大。 【数据规模】 N60　 M3200 题目放宽了“一个主件最多可以有两个附件”这个限制。 问题分析 数据组织方式 依然适用 效率 以物品为节点的树形结构 √ × 以组为元素的序列 × - 我们需要重新组织数据！ 我们回想上题的数据组织方式。 重新安排这些物品的顺序，使得每个附件都紧跟其主件，保证其前面的最近的主件就是它附属的主件。如下图： 数据组织方案二 主件1 附件 主件2 附件 附件 主件3 附件 附件 附件 附件 树 序列 状态F[i][j][k]表示从第i个物品到第n个物品，最多花费j元，k表示i物品前面的主件有没有被购买，的最大价值和。 这样组织数据以后，一个附件能被购买的必要条件是“其前面的最近的主件被购买了”。 算法3 主件1 附件 主件2 附件 附件 主件3 附件 附件 附件 附件 K=0 主件2没有被购买 K=1 主件2有被购买 状态总数　 O(NM*2) 状态转移代价　O(1) 时间复杂度　 O(NM) 算法3 重新组织数据后，我们再次成功地设计出了O(NM)的算法。 【题意描述】 给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，主件可以有任意多附件，可以有多级附件。 很郁闷的金明 【任务】 用不超过M元钱，购买一些物品，使得被购买的物品的总权值最大。 【数据规模】 N60　 M3200 现在的题目在原题的基础条件上不仅增加附件的个数，还出现了多级附件。 问题分析 这是很一般的树！ 一般的树形结构，我们还能不能用前面的数据组织方式呢？ 数据组织方式 依然适用 效率 以物品为节点的树形结构 √ × 以组为元素的序列 × － 附件紧跟其主件的序列 × － 说明这些数据组织方式都不合理，需要再次重新组织数据！ 现在我们再回过头来研究一下前面一种数据组织方式： 把同在一个组的主件放在附件的前面，将树形问题转化到序列上来。 而现在的问题是：　树的高度增加了。 组织数据方案三 考虑：树的先根遍历序。 仔细思考算法3的状态转移： 主件1 附件 主件2 附件 附件 主件3 附件 附件 附件 附件 K=0 迁移到本题中，对于一棵子树，如果我们不购买其根结点，那么其子孙都不必讨论了（因为其子孙节点都不能被购买） 但是我们不能用加一维的方法来记录每个附件的主件是否被购买了！ 　　这一结论似乎很显然，但是我们并不是要在树形结构中