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




 
 
相关试题     算法设计与分析 

  第63题    2016年上半年  
考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6，3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构..

  第63题    2013年上半年  
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个元素ai和aj，使得ai+aj=x。为了求解该问题，首先用归并排序算法对数组A进行从小到大排序；然后判断是否存在ai+aj=x，具..

  第62题    2019年下半年  
采用贪心算法保证能求得最优解的问题是（）。

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



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

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