全部科目 > 软件设计师 >

null null2024年下半年 软件设计师 下午试卷 案例 第 6 题     问题：6.1   用回溯法求解此0-1背包问题，请填充下面伪代码中（1)〜（4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提髙算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND（v,w,k,W）的函数，其中v、w、k和W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点， 该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。 下面给出0-1背包问题的回溯算法伪代码。 函数参数说明如下： W：背包容量；n：物品个数；w:重量数组；v:价值数组；fw:获得最大价值时背包的重量；fp:背包获得的最大价值；X：问题的最优解。 变量说明如下： CW：当前的背包重量；cp：当前获#的价值；k：当前考虑的物品编号；Y:当前已获得的部分解。   问题：6.2   考虑下表所示的实例，假设有3个物品，背包容量为22。 下图是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择/不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品（5),获得的价值 为（6)。. 对于上述实例，若采用穷举法搜索骜个解空间，则搜索树的结点数为（7)，而用了上述回溯法，搜索树的结点数为（8)。     所属分类：         ├  计算机组成与结构    ├ ├  计算机基本工作原理    ├ ├  存储系统    ├ ├  输入输出系统    ├ ├  总线系统    ├ ├  指令系统和计算机体系结构    ├ ├  系统性能评测和可靠性基础    ├ ├  信息安全和病毒防护    ├  程序语言    ├ ├  程序设计语言基本概念    ├ ├  汇编、编译、解释系统    ├ ├  文法分析    ├  操作系统    ├ ├  操作系统定义、分类及功能    ├ ├  进程管理    ├ ├  存储管理    ├ ├  设备管理    ├ ├  文件管理    ├ ├  作业管理    ├  软件工程基础知识    ├ ├  软件工程概述    ├ ├  软件开发项目管理    ├ ├  软件工具与开发环境    ├ ├  软件过程管理    ├ ├  软件质量管理    ├  系统开发与运行    ├ ├  结构化分析和设计    ├ ├  系统设计知识    ├ ├  系统的测试与维护    ├  网络与多媒体基础知识    ├ ├  ISO／OSI网络体系结构    ├ ├  网络互连硬件    ├ ├  网络协议    ├ ├  Internet应用    ├ ├  网络安全    ├ ├  声音及其数字化    ├ ├  图形和图像    ├ ├  动画与视频    ├ ├  多媒体计算机    ├ ├  多媒体网络    ├  数据库技术    ├ ├  数据库基础知识    ├ ├  E-R模型    ├ ├  关系代数和关系模型    ├ ├  SQL语言    ├ ├  关系数据库的规范化    ├ ├  控制功能    ├  算法与数据结构    ├ ├  线性结构    ├ ├  数组、矩阵和广义表    ├ ├  树    ├ ├  图    ├ ├  查找算法    ├ ├  排序算法    ├ ├  算法分析及常用算法    ├  面向对象技术    ├ ├  面向对象的基本概念    ├ ├  面向对象程序设计    ├ ├  面向对象开发技术    ├ ├  面向对象分析与设计方法    ├ ├  设计模式    ├  标准化和知识产权    ├ ├  标准化    ├ ├  知识产权    ├  专业英语    ├ ├  专业英语