全部科目 > 软件设计师 >
2013年上半年 上午试卷 综合知识
第 60 题
知识点 贪心法   实例  
关键词 背包问题   容量   实例  
章/节 计算机软件知识  
 
 
考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如下表所示，并已经按照物品的单位重量价值从大到小排好序，根据物品单位重量价值大优先的策略装入背包中，则采用了（60）设计策略。考虑0/1背包问题（每件物品或者全部放入或者全部不装入背包）和部分背包问题（物品可以部分装入背包），求解该实例，得到的最大价值分别为（61）。
 
  A.  分治
 
  B.  贪心
 
  C.  动态规划
 
  D.  回溯




 
 
相关试题     计算机软件知识 

  第16题    2012年下半年  
某软件项目的活动图如下所示。图中顶点表示项目里程碑，连接顶点的边表示包含的活动，则里程碑（16)在关键路径上，活动FG的松弛时间为（17)。

  第53题    2012年下半年  
设有关系模式R (E，N，M, L, Q),其函数依赖集为F={ E—>N, EM—>Q,M—>L}。则关系模式R达到了（53)；该关系模式（54)。

  第63题    2014年上半年  
某个算法的时间复杂度递归式T(n)=T(n-l)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（62），若问题的规模增加了16倍，则运行时间增加（63）倍。

 
知识点讲解
· 贪心法
· 实例
 
        贪心法
               和动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息作出选择，而且一旦作出选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所作出的选择只是在某种意义上的局部最优。
               用贪心法求解的问题一般具有以下两个重要的性质。
               （1）最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
               （2）贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。
 
        实例
        某考务处理系统有如下功能：
        （1）对考生送来的报名单进行检查。
        （2）对合格的报名单进行检查。
        （3）对阅卷站送来的成绩清单进行检查，并根据考试中心指定的合格标准审定合格者。
        （4）制作考生通知单（内含成绩合格／不合格标志）送给考生。
        （5）按地区、年龄、文化程度、职业和考试级别等进行成绩分类统计和试题难度分析，产生统计分析表。
        该考务处理系统的分层数据流图如下图所示。
        
        考务处理系统分层数据流图



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2026 All Rights Reserved
软考在线版权所有