考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如图8一11所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了(60)设计策略。考虑0／1背包问题(每件物品或者全部装入背包或者不

admin2019-07-12 38

问题考虑下述背包问题的实例。有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)

软件设计师上午基础知识考试

软考中级

数字用户线(DSL)是基于普通电话线的宽带接入技术，可以在铜质双绞线上同时传送数据和话音信号。下列选项中数据速率最高的DSL标准是__________。(2010年上半年试题)

在Windows操作系统中，(37)文件可以帮助域名解析。

交换机命令SwitchA(VLAN)#vtppruning的作用是__________。(2011年下半年试题)

在Windows环境下，租约期满后，DHCP客户端可以向DHCP服务器发送一个_____________报文来请求重新租用IP地址。

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(2)

在CPU中，(3)可用于传送和暂存用户数据，为ALU执行算术逻辑运算提供工作区。

某公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司的网络地址在路由表中只占一行，给它指定的子网掩码必须是(2)。(1)

从长期来看，企业承担责任的大小与其经营业绩呈()

男，45岁，乙肝后肝硬化10年，突然呕血800ml。查体：贫血貌，血压90/60mmHg，脉搏110次/分。腹软，肝未及，脾肋下3cm，血红蛋白60g/L，白细胞3.5×109/L，血小板50×109/L。患者的诊断可能是

胶片的γ值是指

某患犬表现兴奋、流涎、喜食异物、恐水、有攻击性。对此，不宜采取的措施是

法律法规不要求具备一定形式和手续的合同，称为(　　)合同。

下列关于钢吊箱围堰施工的说法，正确的有()。

银监会及其派出机构到各地实地查阅银行业金融机构经营活动的账表，这属于银监会的()。

宗法制（陕西师范大学2012年中国史复试真题；南开大学2013年中国历史真题；福建师范大学2013年中国史综合真题；湖南师范大学2013年历史学综合真题）

Writeanessayof160-200wordsbasedonthefollowingdrawing.Inyouressay,youshould1)describethedrawingbriefly,2)in

Shewalkedroundtothe______ofthecarandstoodsilentlywhileheundidthebootandpickedupherbag.

软件设计师上午基础知识考试

软考中级

数字用户线(DSL)是基于普通电话线的宽带接入技术，可以在铜质双绞线上同时传送数据和话音信号。下列选项中数据速率最高的DSL标准是__________。(2010年上半年试题)

在Windows操作系统中，(37)文件可以帮助域名解析。

交换机命令SwitchA(VLAN)#vtppruning的作用是__________。(2011年下半年试题)

在Windows环境下，租约期满后，DHCP客户端可以向DHCP服务器发送一个_____________报文来请求重新租用IP地址。

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(2)

在CPU中，(3)可用于传送和暂存用户数据，为ALU执行算术逻辑运算提供工作区。

某公司有2000台主机，则必须给它分配(1)个C类网络。为了使该公司的网络地址在路由表中只占一行，给它指定的子网掩码必须是(2)。(1)

从长期来看，企业承担责任的大小与其经营业绩呈()

男，45岁，乙肝后肝硬化10年，突然呕血800ml。查体：贫血貌，血压90/60mmHg，脉搏110次/分。腹软，肝未及，脾肋下3cm，血红蛋白60g/L，白细胞3.5×109/L，血小板50×109/L。患者的诊断可能是

胶片的γ值是指

某患犬表现兴奋、流涎、喜食异物、恐水、有攻击性。对此，不宜采取的措施是

法律法规不要求具备一定形式和手续的合同，称为( )合同。

下列关于钢吊箱围堰施工的说法，正确的有()。

银监会及其派出机构到各地实地查阅银行业金融机构经营活动的账表，这属于银监会的()。

宗法制（陕西师范大学2012年中国史复试真题；南开大学2013年中国历史真题；福建师范大学2013年中国史综合真题；湖南师范大学2013年历史学综合真题）

Writeanessayof160-200wordsbasedonthefollowingdrawing.Inyouressay,youshould1)describethedrawingbriefly,2)in

Shewalkedroundtothe______ofthecarandstoodsilentlywhileheundidthebootandpickedupherbag.

法律法规不要求具备一定形式和手续的合同，称为(　　)合同。