《论文_算法合集之《浅谈数据的合理组织》(定稿)》

《《论文_算法合集之《浅谈数据的合理组织》(定稿)》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈数据的合理组织四川省绵阳南山中学何森【摘要】信息学是一门高深的学科，它正在高速的发展。随着信息学的发展，其题冃中的关系也变得越来越错宗复朵,给我们解题带来困难。对数据进行合理地组织,正是我们面对上述题目时的一种有效手段。木文用几个经典例题从数据的结构和顺序两个方面进行合理组织，达到优化模型或是提升算法效率的H的。介绍了“合理组织数据”在信息学中建立模型和优化算法方面的一些应用，例题包含了动态规划、数据结构、图论类型的题目。目的在于引起读者对于数据的合理组织的关注，并在今后的解题中能积极并灵活地运用这一手段。【关键字】组织数据数据结构动

2、态规划图树序列【正文】【引言】一个简单的例子：给出N个数字（数字会比较大），然后给出一些询问，询问一个数字有没有在给出的N个数字当中。当然我们有很多已知的办法：HASH表、TRIE、预排序+二分査找……这些算法都是通过对数据进行合理的组织而起到了减少工作量的作用。不同的是HASH表和TRIE是利用数据形式的重新组织，而预排序+二分查找是通过对数据顺序的重新组织来达到优化算法的FI的的。我们组织数据，主耍就是通过从“形式”和“顺序”这两个角度来考虑。事实上，这两个方面在实际运用中往往不是独立的，通常需要联合运用。我们已经学习了很多经典的数据

3、结构，它们都是合理组织数据的表现。在优化算法屮有很好表现。对数据组织的合理化，不仅在我们设计算法时能起到优化程序效率的作用，有时，我们在建立解题模型时，合理地组织数据可能给我们提供新的思考角度，从而优化解题模型，例一就是这样的一个例了。[例一]金明的预算方案及其加强版金明的预算方案【题意描述】给出N个物品，每个物品都有一个权值(<50000)和一个价格«10000)o我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，一个主件最多有两个附件，附件没有下一级附件。任务购买一些物品，总价格不超过

4、M,使得被购买的物品的权值之和最大。N<3200M<60【简要分析】我们很容易联想到经典的动态规划之0-1背包问题。如图所示:/lL矽犠直接购买。•数据，如下图:（图1）主件1没有附件,主件2有两个附件，主件3只有一个附件。【算法一】这样，在这棵树上，我们可以设计一个动态规划算法:定义:cos([a]表示a节点所代表的物品的价格score[a]表示a节点所代表的物品的得分状态f[a][b]表示以节点a为根的子树，总共花费不超过b元的最多得分。状态转移方程：f[a][b]=Max{f[cl][bl]+f[c2][b2]+f[c3][b3].

5、..f[ck][bk]}+score[a];具中ci为a的了节点；Zbi=b-cost[aJ;这样枚举的效率显然不高！我们可以用左儿子右兄弟表示法来表示这一棵树，将原树转化成二叉树，则我们在进行状态转移的时候只用考虑给左儿子分配多少钱。left[a]表示a的左儿子i*ight[a]表示a的右儿子f[a][b]=Max{Max{f[left[a]][bleft]+f[right[a]][b-cost[a]-bleft]}+score[a],f[right[a]][b]}这样我们可以得到一个理论I复杂度为0（nm2）的算法，但是对于本题的数据

6、范围來说，这个复杂度并不太理想。【数据组织方案二】上面我们把木题同0・1背包进行了类比。发现対道题之间的差别：附件不能被直接购买。显然，如果题冃屮没有附件，那么本题即为标准的01背包问题。我们回到题H并考虑It特殊性：1.附件没有附件。2.每个主件最多只有2个附件。这样，显然对于（图一）中每一组（主件+附件），可以作为整体考虑。对于每一组，可能的购买方案最多只有：1.什么都不买2.只购买主件3.购买主件和附件14•购买主件和附件25.购买主件和两个附件这样，我们可以借鉴经典的01背包动态规划，把每--组看作一个对象，取值和花费对应最多五种

7、。【算法二】cost[i][k]表示分组后第i个对象的第k种购买方案的花费。weight[i][k]表示分纽后第i个对象的第k种购买方案的总权值。表示前i个对象最多花费j元，能得到的最人权值。F[i][j]=max（F[i-l]（j-cost[i][k]]+weight[i][k]）;其中1<=k<=5且cost[i][k]v=j状态总数：O(NM)转移代价：0(1)这样，我们得到了一个时间复杂度为O(NM)的优秀算法。郁闷的金明【题意描述】给出N个物品，可以直接被购买的称为主件，而不能直接被购买的称为附件，附件只有当其主件被购买了才能被

8、购买，一个主件可以有任意多个附件，附件没有下一级附件。每个物品都有一个权值(<50000)o任务购买一些物品，总价格不超过M,使得被购买的物晶的权值之和最人。N<60M<3200【问题分析】题