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




 
 
相关试题     计算机软件知识 

  第18题    2016年下半年  
某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示相应活动的持续时间（天），则完成该项目的最少时间为（17..

  第63题    2011年上半年  
分治算法设计技术(63)。

  第52题    2009年下半年  
假设有学生S (学号，姓名，性别，入学时间，联系方式)，院系D (院系号，院系 名称，电话号码，负责人）和课程C (课程号，课程名）三个实体，若一名学生属于一个院..

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



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

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