免费智能真题库 > 历年试卷 > 软件设计师 > 2013年上半年 软件设计师 上午试卷 综合知识
  第60题      
  知识点:   贪心法   实例
  关键词:   背包问题   容量   实例        章/节:   计算机软件知识       

 
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如下表所示,并已经按照物品的单位重量价值从大到小排好序,根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部放入或者全部不装入背包)和部分背包问题(物品可以部分装入背包),求解该实例,得到的最大价值分别为(61)。
 
 
  A.  分治
 
  B.  贪心
 
  C.  动态规划
 
  D.  回溯
 
 
 

 
  第63题    2016年上半年  
   68%
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题..
  第64题    2022年下半年  
   42%
采用Dijkstra算法求解下图A点到E点的最短路径,采用的算法设计策略是(64),该最短路径的长度是(65)?。
  第64题    2018年下半年  
   49%
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的..
   知识点讲解    
   · 贪心法    · 实例
 
       贪心法
               和动态规划法一样,贪心法也经常用于解决最优化问题。不过与动态规划法不同的是,贪心法在解决问题的策略上是仅根据当前已有的信息作出选择,而且一旦作出选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所作出的选择只是在某种意义上的局部最优。
               用贪心法求解的问题一般具有以下两个重要的性质。
               (1)最优子结构。当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
               (2)贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来得到。这是贪心法和动态规划法的主要区别。
 
       实例
        某考务处理系统有如下功能:
        (1)对考生送来的报名单进行检查。
        (2)对合格的报名单进行检查。
        (3)对阅卷站送来的成绩清单进行检查,并根据考试中心指定的合格标准审定合格者。
        (4)制作考生通知单(内含成绩合格/不合格标志)送给考生。
        (5)按地区、年龄、文化程度、职业和考试级别等进行成绩分类统计和试题难度分析,产生统计分析表。
        该考务处理系统的分层数据流图如下图所示。
        
        考务处理系统分层数据流图
   题号导航      2013年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第60题    在手机中做本题