全部科目 > 软件设计师 >
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




 
 
相关试题     计算机软件知识 

  第62题    2019年上半年  
已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次..

  第56题    2018年下半年  
给定关系R（A, B,C,D）和S（C,D,E），若关系R与S进行自然连接运算，则运算后的元组属性列数为（55）；关系代数表达式与（56）等价。

  第27题    2012年上半年  
假设一台按字节编址的16位计算机系统，采用虚拟页式存储管理方案，页面的大小为2K，且系统中没有使用快表（或联想存储器)。某用户程序如图a所示，该程序的页面变..

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



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

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