全部科目 > 软件设计师 >
2016年上半年 上午试卷 综合知识
第 64 题
知识点 归并排序   贪心法  
章/节 计算机软件知识  
 
 
考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6，3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为

其中c（i，j）表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c（n,W）。
采用自底向上的动态规划方法求解，得到最大装包价值为（62），算法的时间复杂度为（63）。
若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为（64），算法的时间复杂度为（65）。
 
  A.  11
 
  B.  14
 
  C.  15
 
  D.  16.67




 
 
相关试题     计算机软件知识 

  第37题    2021年上半年  
设用线性探查法解决冲突构造哈希表，且哈希函数为H(key)=key%m，若在该哈希表中查找某关键字e是成功的且与多个关键字进行了比较，则( )。

  第29题    2018年上半年  
若某文件系统的目录结构如下图所示，假设用户要访问文件rw.dll，且当前工作目录为swtools，则该文件的全文件名为（28），相对路径和绝对路径分别为（29）。

  第26题    2013年上半年  
进程资源图如图(a)和(b)所示，其中：图(a)中（25);图(b)中（26)。

 
知识点讲解
· 归并排序
· 贪心法
 
        归并排序
        归并是将两个或两个以上的有序文件合并成为一个新的有序文件。
        归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件，然后进行两两归并，如此重复，直至最后形成一个包含n个记录的有序文件为止。这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。
 
        贪心法
               和动态规划法一样，贪心法也经常用于解决最优化问题。不过与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息作出选择，而且一旦作出选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所作出的选择只是在某种意义上的局部最优。
               用贪心法求解的问题一般具有以下两个重要的性质。
               （1）最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
               （2）贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。



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

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