首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
admin
2021-01-13
53
问题
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包),求解该实例得到的最大价值分别为________(61)。
(60)
选项
A、分治
B、贪心
C、动态规划
D、回溯
答案
B
解析
本题考查贪心算法和背包问题的知识点。
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题能产生整体最优解或者是整体最优解的近似解。
考虑0/1背包问题时,只能放入1、2、3号物品,故总价值为430;考虑部分背包问题时,可以将物品拆分,故放入1、2、3号物品后还可以将编号4的物品部分地装入,使得背包容量尽量地满,故总容量为630。
转载请注明原文地址:https://kaotiyun.com/show/63CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答以下问题,将解答填入答题纸的对应栏内。【说明】某大学欲开发一个基于Web的课程注册系统,该系统的主要功能如下:1.验证输入信息(1)检查学生信息:检查学生输入的所有注册所需信息。如果信息不合法,返回学生信息不合法提示;如果合法
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某汽车数字仪表系统将完成下述功能:(1)通过模.数转换,实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。
阅读下列说明和数据流图,回答问题l至问题3,将解答填入答题纸的对应栏内。【说明】考务处理系统具有如下功能:(1)对考生送来的报名单进行检查。(2)对合格的报名单编好准考证号后将准考证送给考生,并将汇总后的考生名单送给阅卷。(3)对阅卷站送来的成绩
阅读下列说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图16.10所示,现采用组合(Composition)设计模式来构造该公司的组织结构,得到如图16一11所示的类图。其eOC
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求,欲构建数据管理中间件,其主要功能如下:(1)数据管理员可通过中间件进行用户管理、操作管理和权限管理。
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序,算法基
阅读下列说明和图,回答问题1至问题3。【说明】某会议策划公司为了方便客户,便于开展和管理各项业务活动,需要构建一个基于网络的会议预定系统。【需求分析】(1)会议策划公司设有受理部、策划部和其他部门。部门信息包括部门号
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。
如果—个软件是给许多客户使用的,大多数软件厂商要使用几种测试过程来发现那些可能只有最终用户才能发现的错误,(48)测试是由软件的最终用户在一个或多个用户实际使用环境下来进行的。(49)测试是由一个用户在开发者的场所来进行的。测试的目的是寻找错误的原因并改正
编制一个好的程序首先要确保它的正确性和可靠性,除此以外,通常更注重源程序的(9)。还应强调良好的编程风格,例如,选择标识符的名字时应考虑(10);在书写语句时应考虑(11);在书写功能性注解时应考虑(12)。源程序中应包含一些内部文档,以帮助阅读和理解源程
随机试题
自首的分类。
对混合喂养儿选择的最佳非母乳乳品是
A.防病治病,救死扶伤,实行医学人道主义,全心全意为人民健康服务B.全心全意为人民健康服务C.救死扶伤,忠于职守;钻研医术,精益求精;一视同仁,平等对待;语言文明,平等待人;廉洁奉公,遵纪守法;互尊互学,团结协作D.一视同仁,
抗休克治疗的关键措施是去除致休克的病因和下列哪项
货物综合评分法中评标委员会成员应当独立对每个初步评审合格的投标文件的评标因素在规定分值内评价打分,然后按照相应比重或权值计算每个投标人每项评分因素得分及专家汇总平均值。其中货物项目价格评分值占总分值的权值为()。
建设项目后评价的作用是()。
我国第一只开放式基金——( )的诞生,使我国基金业发展实现了从封闭式基金到开放式基金的历史性跨越。
发展心理学研究设计的主要方式有()。
设d=time(),命令?VARTYPE(d)的输出值是
Accordingtocolorpsychologists,certainhuestendtoreflectparticularpersonality______;violet,forexample,indicatesate
最新回复
(
0
)