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




 
 
相关试题     计算机软件知识 

  第26题    2023年上半年  
进程P1、P2、P3、P4、P5和P6的前趋图如下所示：

若用PV操作控制进程P1、P2、P3、P4、P5和P6并发执行的过程，需要设置8个信号量S1、S2、S3、S4、S..

  第20题    2015年下半年  
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生..

  第53题    2015年上半年  
（53）算法采用模拟生物进化的三个基本过程“繁殖（选择）-> 交叉（重组）->变异（突变）”。

 
知识点讲解
· 贪心法
 
        贪心法
               和动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息作出选择，而且一旦作出选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所作出的选择只是在某种意义上的局部最优。
               用贪心法求解的问题一般具有以下两个重要的性质。
               （1）最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
               （2）贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。



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

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