《算法合集之浅谈数据的合理组织》由会员分享，可在线阅读，更多相关《算法合集之浅谈数据的合理组织（15页珍藏版）》请在金锄头文库上搜索。
1、浅谈数据的合理组织四川省绵阳南山中学何森【摘要】信息学是一门高深的学科，它正在高速的发展。随着信息学的发展，其题目 中的关系也变得越来越错宗复杂,给我们解题带来困难。对数据进行合理地组织， 正是我们面对上述题目时的一种有效手段。本文用几个经典例题从数据的结构和顺序两个方面进行合理组织，达到优化 模型或是提升算法效率的目的。介绍了 “合理组织数据”在信息学中建立模型和 优化算法方面的一些应用，例题包含了动态规划、数据结构、图论类型的题目。 目的在于引起读者对于数据的合理组织的关注，并在今后的解题中能积极并灵活 地运用这一手段。【关键字】组织数据 数据结构 动态规划 图 树 序列【正文】【引言】一
2、个简单的例子：给出N个数字(数字会比较大)，然后给出一些询问，询问一个数字有没有在 给出的N个数字当中。当然我们有很多已知的办法：HASH表、TRIE、预排序+二分查找这些算法都是通过对数据进行合理的组织而起到了减少工作量的作用。不同的是HASH表和TRIE是利用数据形式的重新组织，而预排序+二分查找是 通过对数据顺序的重新组织来达到优化算法的目的的。我们组织数据，主要就是 通过从“形式”和“顺序”这两个角度来考虑。事实上，这两个方面在实际运用 中往往不是独立的，通常需要联合运用。我们已经学习了很多经典的数据结构，它们都是合理组织数据的表现。在优 化算法中有很好表现。对数据组织的合理化，不仅在
3、我们设计算法时能起到优化 程序效率的作用，有时，我们在建立解题模型时，合理地组织数据可能给我们提 供新的思考角度，从而优化解题模型，例一就是这样的一个例子。例一金明的预算方案及其加强版金明的预算方案【题意描述】给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们 称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当 其主件被购买了才能被购买，一个主件最多有两个附件，附件没有下一级附件。 任务购买一些物品，总价格不超过M,使得被购买的物品的权值之和最大。N3200 M60【简要分析】我们很容易联想到经典的动态规划之0-1背包问题。 但是题目与背包却有一
4、些差别：附件不能被直接购买。【对数据的初步组织】主件与附件之间是树形的关系。组织一下数据，如下图:如图所示：主件1没有附件，主件2有两个附件，主件3只有一个附件。【数据组织方案一】假设我们忽略数据的特殊性，单从树结构考虑，我们容易想到的一个算法是： 给所有主件加上一个“级超主件”，把原来的所有主件都变成“超级主件”的附 件，如下图：【算法一】这样，在这棵树上，我们可以设计一个动态规划算法： 定义：costa表示a节点所代表的物品的价格 scorea表示a节点所代表的物品的得分 状态fab表示以节点a为根的子树，总共花费不超过b元的最多得分。 状态转移方程：fab=Maxfc lbl +fc2b
5、2+fc3 b3.fckbk +scorea;其中ci为a的子节点；Sbi=b-costa;这样枚举的效率显然不高！我们可以用左儿子右兄弟表示法来表示这一棵树，将原树转化成二叉树，则我们 在进行状态转移的时候只用考虑给左儿子分配多少钱。lefta表示a的左儿子 righta表示a的右儿子 fab=MaxMaxfleftableft+frightab-costa-bleft+scorea,frighta b这样我们可以得到一个理论1复杂度为0(nm2)的算法，但是对于本题的数据范围 来说，这个复杂度并不太理想。【数据组织方案二】上面我们把本题同0-1背包进行了类比。发现两道题之间的差别：附件不能
6、被直 接购买。显然，如果题目中没有附件，那么本题即为标准的01背包问题。我们回到题目并考虑其特殊性：1 附件没有附件。2. 每个主件最多只有2个附件。这样，显然对于(图一)中每一组(主件+附件)，可以作为整体考虑。对于每一组，可能的购买方案最多只有：1. 什么都不买2. 只购买主件3. 购买主件和附件14. 购买主件和附件25. 购买主件和两个附件这样，我们可以借鉴经典的01背包动态规划，把每一组看作一个对彖，取值和 花费对应最多五种。【算法二】costik表示分组后第i个对彖的第k种购买方案的花费。 weightik表示分组后第i个对彖的第k种购买方案的总权值。表示前i个对彖最多花费j元，能
7、得到的最大权值。Fi j=max(Fi-l j -costi k+weighti k);其中 l=k=5 且 costik=j状态总数：O(NM)转移代价：0(1)这样，我们得到了一个时间复杂度为O(NM)的优秀算法。郁闷的金明【题意描述】给出N个物品，可以直接被购买的称为主件，而不能直接被购买的称为附件， 附件只有当其主件被购买了才能被购买，一个主件可以有任意多个附件，附件没 有下一级附件。每个物品都有一个权值(50000)。任务购买一些物品，总价格不超过M,使得被购买的物品的权值之和最大。N60M=costi),Fi+1 0 0情况II：第i个物品是附件如果 k=l Fijk= MaxFi
8、+lj-costil+weighti (j=cost订,Fi+ljl 如果 k=0Fi|jk=Fi+lj0状态总数：O(NM)转移代价：0(1)时间复杂度同样是O(NM)。很郁闷的金明【题意描述】给出N个物品，可以直接被购买的称为主件，而不能直接被购买的称为附件， 附件只有当其主件被购买了才能被购买，一个主件可以有任意多个附件，附件可 以有多级，也就是说如果某个物品是附件，那么它还有可能有附属于它的下一级 附件。每个物品都有一个权值(50000)。任务购买一些物品，总价格不超过M,使得被购买的物品的权值之和最大。N60M3200【问题分析】现在题目在原题的基础上不仅放宽了附件的个数，还放宽了附
9、件的层数，如图所 示：从上图中，我们可以对本题有一个感性的认识：关系又“宽”又“深”。 我们依然试着从前面的题目中寻找算法：我们可以直接套用算法1,因为该算法正好将数据作为树结构来进行处理。而利 用了题目特殊条件的算法2和算法3,直接套用算法肯定是行不通的。但是他们都很有启发性：抛弃树形的结构，重新组织成线形。 现在的题目是不是也可以类似解决呢？【组织数据方案四】算法3相对来说比较算法2更加一般,所以现在我们再回过头来研究一下算法3, 希望在分析过程中找到一些灵感。回忆算法3的思路：把同在一个组的主件放在附件的前面，利用动态规划“加一维”的思想，顺利地 实现了将问题转化到序列上来。关键字：主件
10、在前序列动态规划我们联想到利用树的先根遍历序，而且正好满足上面的关系。但是这样有什么好处吗？还能进行动态规划吗？怎样设计状态才能传递父节点 的状态呢？我们再回过去看算法3的状态转移：假设当前状态是Fijk,且k=0。如果i是附件，那么实际上在到达下一个主件以前,i后面的附件是都不会被购 买的。K=0主件1附件附件主件2附件a附件b附件c主件3上图中，对于附件a,实际上一个k=0的状态传递下去是没有意义的，因为附件 b和附件c也必然不能被购买。思考并总结上面的结论.為于一个孑件，我们如果不购买的话，那么其附件我们都不用考虑，而直接“跳 ”到下一个主件。我们把它应用到本题中来：重要结论 我们考虑一
11、棵子树的时候，如果我们不购买其根节点，那么其子树 中所有节点我们都不必讨论了。这一结论似乎很显然，但是我们并不是要在树结构中用这一结论。正如上面提到 的，我们要在树的先根遍序上进行动态规划，而这一结论正是我们成功的关键。【算法4】根据前面的思考，我们先依次求出每棵树的先根遍历序，并保存在同一个序列 list中。为了利用上面的结论，我们还要求出以节点i为根的子树的节点总数countio 现在我们来设计动态规划算法：定义：costi表示第i个物品的价格 weighti表示第i个物品的权值 表示从第i个物品到第n个物品，最多花费j元，能得到的最大权值和。状态转移：对于一个节点，我们考虑是否购买它：购
12、买：那么我们继续考虑它后面的节点不购买：那么我们跳过它的子孙节点方程如下：Fij=MaxFi+lj-costlisti+weightlisti,Fi+countlistij这个算法依然是O(NM)的，很完美地解决了本题。并且，这个算法模型对于以 前有很多类似的树形动态规划题目都适用，这是我们在分析本题的过程中的意外 收获。【小结】这是一道很有启发性的道目。反思这一题的几个不同难度的版本，不难发现我们 最终都用线形模型上的动态规划取代了容易想到的树形动态规划算法。我们再次 分析前面的算法，试图发现其中内在的一些东西。其实我们这个题主要就是对于 树形结构和线形结构的选择，所以我们对比算法4和算法1:不难发现，相比算法4,算法1其实多出的操作就是枚举分配给左儿子多少钱。树形须进行“分流” 序列直接分配到后面而在线形的序列上，没有用的钱自然地被分配给后面的元素。也就是说：树的形 态决定了在状态转移的时候要进行额外的枚举。这正是树形动态规划算法的瓶颈 所在！而我们利用树的先根遍历序将转树形转化为线形序列，成功地避免了树形 形态的限制，正是合理地组织数据。我们得到的启示：凭第一感觉想出来的模型不一定是最好的，对于一个题目，我 们充分挖掘其数据关系并加以利
