首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如图8一11所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如图8一11所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不
admin
2019-07-12
53
问题
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如图8一11所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包),求解该实例得到的最大价值分别为(61)。
(61)
选项
A、605和630
B、605和605
C、430和630
D、630和430
答案
C
解析
本题考查贪心算法和背包问题的知识点。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。采用0/1背包考虑该问题时,只能放入1、2、3号物品,故总价值为430,采用部分背包可以将物品拆分,故放入1、2、3号物品后还可以将编号4的物品部分的装入,使得背包容量尽量的满,故总容量为630。
转载请注明原文地址:https://kaotiyun.com/show/I6CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
双极型AMI编码经过一个噪声信道,接收的波形如图所示,那么出错的是第(15)位。
有多种方案可以在一台服务器中安装Windows和Linux两种网络操作系统,其中可以同时运行Windows和Linux两种网络操作系统的方案是____________。
SNMPv2MIB扩展和细化了MIB-II中定义的管理对象,又增加了新的管理对象。扩展和新增的管理对象不包括__________。
攻击者通过发送一个目的主机已经接收过的报文来达到攻击目的,这种攻击方式属于(42)________________攻击。
若内存地址区间为4000H~43FFH,每个存贮单元可存储16位二进制数,该内存区域由4片存储器芯片构成,则构成该内存所用的存储器芯片的容量是(4)。
在Linux操作系统中,存放用户账号加密口令的文件是__________。(2009年下半年试题)
计算机采用分级存储体系的主要目的是为了解决()的问题。
工作站A的IP地址是202,117.17.24/28,而工作站B的IP地址是202.117.17.100/28,当两个工作站直接相连时不能通信,怎样修改地址才能使得这两个工作站可以互相通信?(56)。
填充流程图中①的判断条件。中缀表达式(A+B-C*D)*(E-F)/G经该流程图处理后的输出是什么?[*]
随机试题
熟悉各种传染病的潜伏期最重要的意义是
女,20岁。上前牙松动3年。检查:上切牙松动Ⅱ度扇形移位,口腔卫生较好,初步印象为局限性青少年牙周炎。若已确诊,其可能还具有的特征如下,但不包括
肝硬化门脉高压诊断最具有特征意义的表现是()
《大气污染物综合排放标准》规定的最高允许排放速率,新污染源分为(),现有污染源分为()。
单位银行卡账户的资金必须由其一般账户款账户转账存入。()
下列各项对企业资源能力的价值链分析表述中,正确的有()。
在教育心理学的研究中,通过其他有关材料,间接了解被试者的心理活动的方法是()
党对公安工作领导的(),就是要求公安机关必须无条件地置于党中央及各级党委的领导之下,不得以任何理由或借口削弱、抵制、损害或者摆脱党的领导。
“了”即是助词,也是语气词。(上海外国语大学2016)简述“了”在句中有几种出现的位置,分别是表示什么语法意义的。
设n阶实对称矩阵A满足条件A2+6A+8E=O,且A+tE是正定矩阵,则t的取值范围为_______.
最新回复
(
0
)