首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
admin
2021-01-13
62
问题
(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和Java代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(连不用的功能)都要全面初始化的话,会连带影响到应用软件要花很多时间才能启动。因此常将程序设
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】一个新的音像商店准备向比较广泛的人群出租录像带和光碟。该商店的管理决定在计算机系统的支持下来运作。音像商店在货架上存放着题材广泛的当前流行的电影库。由于同一个电影片名可能有于不同
阅读下列说明和图,回答问题l至问题3,将解答填入答题纸对应栏内。【说明】某城市拟开发一个基于web的城市黄页,公开发布该城市重要的组织或机构(以F统称为客户)的基本信息,方便城市生活。该系统的主要功能描述如下:(1)搜索信息:任何使用Internet的
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方,通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下:(1)注册。顾客在买药之前,必须先在网上药店注册。注册过程中需填写顾客资料
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某医院欲开发病人监控系统。该系统通过各种设备监控病人的生命体征,并在生命体征异常时向医生和护理人员报警。该系统的主要功能如下:(1)本地监控:定期获取病人的生命特征,如体温、血
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
某基于微处理器的住宅系统,使用传感器(如红外探头、摄像头等)来检测各种意外情况,如非法进入、火警、水灾等。房主可以在安装该系统时配置安全监控设备(如传感器、显示器、报警器等),也可以在系统运行时修改配置,通过录像机和电视机监控与系统连接的所有传感
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|19,则以下字符串中,不能被该DFA接受的是(28),与该DFA等价的正规式是(29)。(其中,ε表示空字符)①3857 ②1.2E+5 ③-123. ④.576
编制一个好的程序首先要确保它的正确性和可靠性,除此以外,通常更注重源程序的(9)。还应强调良好的编程风格,例如,选择标识符的名字时应考虑(10);在书写语句时应考虑(11);在书写功能性注解时应考虑(12)。源程序中应包含一些内部文档,以帮助阅读和理解源程
在文件系统中,下列关于当前目录(工作目录)的叙述中,不正确的是(22)。
随机试题
下列哪项不是狂病的特征
男性,20岁,2个月前上腹部被车把撞伤,出现上腹部持续性胀痛,逐渐膨起,餐后加重,并放射至腰背部,伴有恶心呕吐。查体:体温38℃,上腹部偏左侧明显膨隆,可扪及界限不清、固定、有触痛肿物,直径6cm
背景材料某单位办公楼建筑面积24000m2,采用现浇混凝土框架结构,基础为筏板式基础,地下2层,地上15层。基础埋深8.4m,地下水位-2.6m,现场地坪标高-0.8m。基坑开挖到设计标高后,施工单位和监理单位立即对基坑进行了验槽,并对基底进行了
数据1,3,5,x,2,6的中位数是3,则x=____________.
甲在1998年5月5日实施了一个犯罪行为,对这个犯罪行为,旧刑法规定的刑罚较轻,新刑法规定的刑罚较重,根据有关规定,甲的犯罪行为适用()。
阅读下面材料,并回答问题:材料1:4岁的玛丽和爸爸的电话交谈父亲:玛丽,妈妈在家吗?玛丽:(不说话,点头)父亲:玛丽,我可以和妈妈说话吗?玛丽:(再次不语点头)材料2:16岁的萨布丽娜的早晨
HowdoyouexplaineconomicsinplainEnglish?TheFederalReserveBankofNewYorkhasbeenansweringthequestionwithaneven
将考生文件夹下ZOOM文件夹中的文件MACRO.OLD设置成隐藏属性。
What’sthemaintopicofthemonologue?
WhatdayisDr.Miller’sofficeclosed?
最新回复
(
0
)