全部科目 > 软件设计师 >

null null2024年下半年 软件设计师 下午试卷 案例 第 2 题   设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。 采用回溯法来求解该问题： 首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，···，m} 将解空间用树形结构表示。 接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(c11)是否超过上限(cc)，重量(w11) 是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(c11+c21)是否超过上限(cc)，重量(w11+w21)是否比当前已知的解(最小重量)大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。   问题：2.1   【C代码】     所属分类：         ├  计算机组成与结构    ├ ├  计算机基本工作原理    ├ ├  存储系统    ├ ├  输入输出系统    ├ ├  总线系统    ├ ├  指令系统和计算机体系结构    ├ ├  系统性能评测和可靠性基础    ├ ├  信息安全和病毒防护    ├  程序语言    ├ ├  程序设计语言基本概念    ├ ├  汇编、编译、解释系统    ├ ├  文法分析    ├  操作系统    ├ ├  操作系统定义、分类及功能    ├ ├  进程管理    ├ ├  存储管理    ├ ├  设备管理    ├ ├  文件管理    ├ ├  作业管理    ├  软件工程基础知识    ├ ├  软件工程概述    ├ ├  软件开发项目管理    ├ ├  软件工具与开发环境    ├ ├  软件过程管理    ├ ├  软件质量管理    ├  系统开发与运行    ├ ├  结构化分析和设计    ├ ├  系统设计知识    ├ ├  系统的测试与维护    ├  网络与多媒体基础知识    ├ ├  ISO／OSI网络体系结构    ├ ├  网络互连硬件    ├ ├  网络协议    ├ ├  Internet应用    ├ ├  网络安全    ├ ├  声音及其数字化    ├ ├  图形和图像    ├ ├  动画与视频    ├ ├  多媒体计算机    ├ ├  多媒体网络    ├  数据库技术    ├ ├  数据库基础知识    ├ ├  E-R模型    ├ ├  关系代数和关系模型    ├ ├  SQL语言    ├ ├  关系数据库的规范化    ├ ├  控制功能    ├  算法与数据结构    ├ ├  线性结构    ├ ├  数组、矩阵和广义表    ├ ├  树    ├ ├  图    ├ ├  查找算法    ├ ├  排序算法    ├ ├  算法分析及常用算法    ├  面向对象技术    ├ ├  面向对象的基本概念    ├ ├  面向对象程序设计    ├ ├  面向对象开发技术    ├ ├  面向对象分析与设计方法    ├ ├  设计模式    ├  标准化和知识产权    ├ ├  标准化    ├ ├  知识产权    ├  专业英语    ├ ├  专业英语