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

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

ID:49561158

大小:632.00 KB

页数:31页

时间:2020-02-07

算法合集之《浅谈数据的合理组织》.ppt_第1页
算法合集之《浅谈数据的合理组织》.ppt_第2页
算法合集之《浅谈数据的合理组织》.ppt_第3页
算法合集之《浅谈数据的合理组织》.ppt_第4页
算法合集之《浅谈数据的合理组织》.ppt_第5页
资源描述:

《算法合集之《浅谈数据的合理组织》.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、四川省绵阳南山中学何森浅谈数据的合理组织引子题目越来越难——数据关系越来越复杂!对组织数据的要求越来越高!合理组织在解题中越来越重要!【题意描述】给出N个物品,每个物品都有一个权值(<50000)和一个价格(<10000)。我们称可以直接被购买的物品为主件,称不能被直接购买的物品为附件,附件只有当其主件被购买了才能被购买,一个主件最多有两个附件,附件没有下一级附件。【任务】用不超过M元钱,购买一些物品,使得被购买的物品的总权值最大。金明的预算方案【数据规模】N<60M<3200题目中给出的主件与附件

2、间形成树形结构,而所有的物品间形成森林结构。为了方便起见,我们给所有的主件都加上一个“上级主件”,这样,所有的物品形成了一棵树。数据的初步组织树形动态规划算法!算法1状态F[i][j]表示给以i为根的子树,总共花费不超过j元,所能取得的最大权值和。???枚举量太大,效率不高!总花费不超过j用左儿子右兄弟表示法来表示这一棵树!时间复杂度为O(NM2)状态总数O(MN)状态转移代价O(M)N*M*M<=6*108,不太理想。状态F[i][j]表示以i为根的子树总共花费j元能获得的最大权值和。我们只需要枚

3、举给左子树分配多少钱,剩下的钱都分给右子树。我们把配套的主件和附件看成一组。这样,显然对于每一组,可能的购买方案最多只有如下五种:我们换一种数据组织方式1.附件没有附件。2.每个主件最多只有两个附件。考虑本题特殊条件:1.什么都不买2.只购买主件3.购买主件和附件14.购买主件和附件25.全购买类似经典的0-1背包问题!组织数据后,我们可以得到复杂度为O(NM)的优秀算法状态总数O(MN)状态转移代价O(1)郁闷的金明【题意描述】给出N个物品,每个物品都有一个权值(<50000)和一个价格(<100

4、00)。我们称可以直接被购买的物品为主件,称不能被直接购买的物品为附件,附件只有当其主件被购买了才能被购买,主件可以有任意多附件,附件没有下一级附件。【任务】用不超过M元钱,购买一些物品,使得被购买的物品的总权值最大。【数据规模】N<60M<3200题目放宽了“一个主件最多可以有两个附件”这个限制。问题分析数据组织方式依然适用效率以物品为节点的树形结构√×以组为元素的序列×-我们需要重新组织数据!我们回想上题的数据组织方式。重新安排这些物品的顺序,使得每个附件都紧跟其主件,保证其前面的最近的主件就是

5、它附属的主件。如下图:数据组织方案二主件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)的算法。【

6、题意描述】给出N个物品,每个物品都有一个权值(<50000)和一个价格(<10000)。我们称可以直接被购买的物品为主件,称不能被直接购买的物品为附件,附件只有当其主件被购买了才能被购买,主件可以有任意多附件,可以有多级附件。很郁闷的金明【任务】用不超过M元钱,购买一些物品,使得被购买的物品的总权值最大。【数据规模】N<60M<3200现在的题目在原题的基础条件上不仅增加附件的个数,还出现了多级附件。问题分析这是很一般的树!一般的树形结构,我们还能不能用前面的数据组织方式呢?数据组织方式依然适用效率

7、以物品为节点的树形结构√×以组为元素的序列×-附件紧跟其主件的序列×-说明这些数据组织方式都不合理,需要再次重新组织数据!现在我们再回过头来研究一下前面一种数据组织方式:把同在一个组的主件放在附件的前面,将树形问题转化到序列上来。而现在的问题是:树的高度增加了。组织数据方案三考虑:树的先根遍历序。仔细思考算法3的状态转移:主件1附件主件2附件附件主件3附件附件附件附件K=0迁移到本题中,对于一棵子树,如果我们不购买其根结点,那么其子孙都不必讨论了(因为其子孙节点都不能被购买)但是我们不能用加一维的方

8、法来记录每个附件的主件是否被购买了!这一结论似乎很显然,但是我们并不是要在树形结构中运用这一结论。正如上面提到的,我们要在树的先根遍序上进行动态规划,而这一结论正是我们成功的关键。状态F[i][j]表示在遍历序列中从第i个物品到第n个物品,最多花费j元,能得到的最大权值和。算法4主件1附件主件2附件附件主件3附件附件附件附件没有购买根结点!直接“跳”过去!状态总数O(NM)状态转移代价O(1)时间复杂度O(NM)重新组织数据后,我们再一次优解此题。算法4这样,实际上我

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。