搜索
浅谈数据的合理组织四川省绵阳南山中学何森【摘要】信息学是一门高深的学科，它正在高速的发展。随着信息学的发展，其题目中的关系也变得越来越错宗复杂，给我们解题带来困难。对数据进行合理地组织，正是我们面对上述题目时的一种有效手段。本文用几个经典例题从数据的结构和顺序两个方面进行合理组织，达到优化模型或是提升算法效率的目的。介绍了“合理组织数据”在信息学中建立模型和优化算法方面的一些应用，例题包含了动态规划、数据结构、图论类型的题目。目的在于引起读者对于数据的合理组织的关注，并在今后的解题中能积极并灵活地运用这一手段。【关键字】组织数据数据结构动态规划图树序列【正文】【引言】一个简单的例子：给出N个数字(数字会比较大)，然后给出一些询问，询问一个数字有没有在给出的N个数字当中。当然我们有很多已知的办法：HASH表、TRIE、预排序+二分查找……这些算法都是通过对数据进行合理的组织而起到了减少工作量的作用。不同的是HASH表和TRIE是利用数据形式的重新组织，而预排序＋二分查找是通过对数据顺序的重新组织来达到优化算法的目的的。我们组织数据，主要就是通过从“形式”和“顺序”这两个角度来考虑。事实上，这两个方面在实际运用中往往不是独立的，通常需要联合运用。我们已经学习了很多经典的数据结构，它们都是合理组织数据的表现。在优化算法中有很好表现。对数据组织的合理化，不仅在我们设计算法时能起到优化程序效率的作用，有时，我们在建立解题模型时，合理地组织数据可能给我们提供新的思考角度，从而优化解题模型，例一就是这样的一个例子。［例一］金明的预算方案及其加强版金明的预算方案【题意描述】给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，一个主件最多有两个附件，附件没有下一级附件。任务购买一些物品，总价格不超过M，使得被购买的物品的权值之和最大。N3200M60【简要分析】我们很容易联想到经典的动态规划之0-1背包问题。但是题目与背包却有一些差别：附件不能被直接购买。【对数据的初步组织】主件与附件之间是树形的关系。组织一下数据，如下图：（图1）如图所示：主件1没有附件，主件2有两个附件，主件3只有一个附件。【数据组织方案一】假设我们忽略数据的特殊性，单从树结构考虑，我们容易想到的一个算法是：给所有主件加上一个“级超主件”，把原来的所有主件都变成“超级主件”的附件，如下图：(图2)【算法一】这样，在这棵树上，我们可以设计一个动态规划算法：定义：cost[a]表示a节点所代表的物品的价格score[a]表示a节点所代表的物品的得分状态f[a][b]表示以节点a为根的子树，总共花费不超过b元的最多得分。状态转移方程：f[a][b]=Max{f[c1][b1]+f[c2][b2]+f[c3][b3]...f[ck][bk]}+score[a];其中ci为a的子节点；∑bi=b-cost[a];这样枚举的效率显然不高！我们可以用左儿子右兄弟表示法来表示这一棵树，将原树转化成二叉树，则我们在进行状态转移的时候只用考虑给左儿子分配多少钱。left[a]表示a的左儿子right[a]表示a的右儿子f[a][b]=Max{Max{f[left[a]][bleft]+f[right[a]][b-cost[a]-bleft]}+score[a],f[right[a]][b]}这样我们可以得到一个理论1复杂度为O(NM2)的算法，但是对于本题的数据范围来说，这个复杂度并不太理想。【数据组织方案二】上面我们把本题同0-1背包进行了类比。发现两道题之间的差别：附件不能被直接购买。显然，如果题目中没有附件，那么本题即为标准的01背包问题。我们回到题目并考虑其特殊性：1.附件没有附件。2.每个主件最多只有2个附件。这样，显然对于（图一）中每一组（主件＋附件），可以作为整体考虑。对于每一组，可能的购买方案最多只有：1.什么都不买2.只购买主件3.购买主件和附件14.购买主件和附件25.购买主件和两个附件这样，我们可以借鉴经典的01背包动态规划，把每一组看作一个对象，取值和花费对应最多五种。【算法二】cost[i][k]表示分组后第i个对象的第k种购买方案的花费。weight[i][k]表示分组后第i个对象的第k种购买方案的总权值。F[i][j]表示前i个对象最多花费j元，能得到的最大权值。F[i][j]=max(F[i-1][j-cost[i][k]]+weight[i][k]);其中1=k=5且cost[i][k]=j状态总数：O(NM)转移代价：O(1)这样，我们得到了一个时间复杂度为O(NM)的优秀算法。郁闷的金明【题意描述】给出N个物品，可以直接被购买的称为主件，而不能直接被购买的称为附件，附件只有当其主件被购买了才能被购买，一个主件可以有任意多个附件，附件没有下一级附件。每个物品都有一个权值(50000)。任务购买一些物品，总价格不超过M，使得被购买的物品的权值之和最大。N60M3200【问题分析】题目放宽了“一个主件最多可以有两个附件”这个限制，其它条件不变。自然，我们当然尝试用原题中的算法来套本题。实际上，这时候原来的算法1依然适用，复杂度仍为O(NM2)。但是对于利用原题条件特殊性的算法2，一个对象的取值可能达到N的组合级别，所以我们大可放弃对于算法2的讨论。1参见《算法艺术与信息学竞赛》贪食的九头龙中对算法复杂度的分析我们是否有合理的组织数据的办法呢？【数据组织方案三】重新安排这些物品的顺序，使得每个附件都紧跟其主件，保证其左边的第一个主件就是它附属的主件。如下图：这样做的好处是：一个附件能被购买的必要条件就是在其前面的最近的主件被购买了。看似和原来的条件没有什么变化，但是实际上我们给节点的位置已经加上了一个限制。原本树上的问题经过我们“合理地组织数据以后”，成功地转化成了一个序列上的问题。【算法3】这样组织数据以后，我们利用前面提到的条件“一个附件能被购买的必要条件是其前面的最近的主件被购买了”，可以轻松地设计动态规划算法：定义：cost[i]表示第i个物品的价格weight[i]表示第i个物品的权值F[i][j][k]表示从第i个物品到第n个物品，最多花费j元，第i个物品前的主件有(k=1)没有(k=0)被购买。分情况进行状态转移：情况I：第i个物品是主件F[i][j][k]=Max{F[i+1][j-cost[i]][1]+weight[i](j=cost[i]),F[i+1][j][0]}情况II：第i个物品是附件如果k=1F[i][j][k]=Max{F[i+1][j-cost[i]][1]+weight[i](j=cost[i]),F[i+1][j][1]}如果k=0F[i][j][k]=F[i+1][j][0]状态总数：O(NM)转移代价：O(1)时间复杂度同样是O(NM)。很郁闷的金明【题意描述】给出N个物品，可以直接被购买的称为主件，而不能直接被购买的称为附件，附件只有当其主件被购买了才能被购买，一个主件可以有任意多个附件，附件可以有多级，也就是说如果某个物品是附件，那么它还有可能有附属于它的下一级附件。每个物品都有一个权值(50000)。任务购买一些物品，总价格不超过M，使得被购买的物品的权值之和最大。N60M3200【问题分析】现在题目在原题的基础上不仅放宽了附件的个数，还放宽了附件的层数，如图所示：从上图中，我们可以对本题有一个感性的认识：关系又“宽”又“深”。我们依然试着从前面的题目中寻找算法：我们可以直接套用算法1，因为该算法正好将数据作为树结构来进行处理。而利用了题目特殊条件的算法2和算法3，直接套用算法肯定是行不通的。但是他们都很有启发性：抛弃树形的结构，重新组织成线形。现在的题目是不是也可以类似解决呢？【组织数据方案四】算法3相对来说比较算法2更加一般，所以现在我们再回过头来研究一下算法3，希望在分析过程中找到一些灵感。回忆算法3的思路：把同在一个组的主件放在附件的前面，利用动态规划“加一维”的思想，顺利地实现了将问题转化到序列上来。关键字：主件在前序列动态规划我们联想到利用树的先根遍历序，而且正好满足上面的关系。但是这样有什么好处吗？还能进行动态规划吗？怎样设计状态才能传递父节点的状态呢？我们再回过去看算法3的状态转移：假设当前状态是F[i][j][k]，且k=0。如果i是附件，那么实际上在到达下一个主件以前，i后面的附件是都不会被购买的。上图中，对于附件a，实际上一个k=0的状态传递下去是没有意义的，因为附件b和附件c也必然不能被购买。思考并总结上面的结论：对于一个主件，我们如果不购买的话，那么其附件我们都不用考虑，而直接“跳”到下一个主件。我们把它应用到本题中来：重要结论我们考虑一棵子树的时候，如果我们不购买其根节点，那么其子树中所有节点我们都不必讨论了。这一结论似乎很显然，但是我们并不是要在树结构中用这一结论。正如上面提到的，我们要在树的先根遍序上进行动态规划，而这一结论正是我们成功的关键。【算法4】根据前面的思考，我们先依次求出每棵树的先根遍历序，并保存在同一个序列list[]中。为了利用上面的结论，我们还要求出以节点i为根的子树的节点总数count[i]。现在我们来设计动态规划算法：定义：cost[i]表示第i个物品的价格weight[i]表示第i个物品的权值F[i][j]表示从第i个物品到第n个物品，最多花费j元，能得到的最大权值和。状态转移：对于一个节点，我们考虑是否购买它：购买：那么我们继续考虑它后面的节点不购买：那么我们跳过它的子孙节点方程如下：F[i][j]=Max{F[i+1][j-cost[list[i]]]+weight[list[i]],F[i+count[list[i]]][j]}这个算法依然是O(NM)的，很完美地解决了本题。并且，这个算法模型对于以前有很多类似的树形动态规划题目都适用，这是我们在分析本题的过程中的意外收获。【小结】这是一道很有启发性的道目。反思这一题的几个不同难度的版本，不难发现我们最终都用线形模型上的动态规划取代了容易想到的树形动态规划算法。我们再次分析前面的算法，试图发现其中内在的一些东西。其实我们这个题主要就是对于树形结构和线形结构的选择，所以我们对比算法4和算法1:不难发现，相比算法4，算法1其实多出的操作就是枚举分配给左儿子多少钱。而在线形的序列上，没有用的钱自然地被分配给后面的元素。也就是说：树的形态决定了在状态转移的时候要进行额外的枚举。这正是树形动态规划算法的瓶颈所在！而我们利用树的先根遍历序将转树形转化为线形序列，成功地避免了树形形态的限制，正是合理地组织数据。我们得到的启示：凭第一感觉想出来的模型不一定是最好的，对于一个题目，我们充分挖掘其数据关系并加以利用，合理地组织数据并且尝试用已有的知识来解决，推陈出新，才能不断地进步。前面我们在树据的组织结构上进行了合理地安排，成功地对于每一次加强的题目都设计出了优秀的算法，下面，我们来看一看“顺序”的合理安排的例子：［例二］树的果实【题意描述】给出一棵有N个节点的有根树（根为1号节点），每个节点有权值。要求对于每一个节点，求：1.其子树中权值比该节点大的节点总数2.树上除其子孙节点外比该节点大的节点总数3.从根节点到该节点路径中比该节点大的节点总数其中(1=N=105)【问题分析】对于要求的后面两个值，我们很容易想到O(Nlog2(N))的算法：树上除其子孙节点外比该节点大的节点总数：直接排序，在待统计节点前的与该节点权值不同的个数再减去问题1的答案即为所求。从根节点到该节点路径中比该节点大的节点总数：以权值为关键字构造线段树(若权值大可行离散化处理)，深度优先遍历树上节点，用栈记录下到节点的路径，并把当前节点插入线段树，在线段树中我们记录区间的元素个数，当前节点权值到最大权值这个区间中元素个数即为所求，我们再递归处理子树，在子树访问完毕后还须把该节点从