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

admin2019-07-12 45

问题考虑下述背包问题的实例。有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://www.kaotiyun.com/show/I6CZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

设信道带宽为3400Hz，调制为4种不同的码元，根据奈奎斯特定理，理想信道的数据速率为______。(2008年上半年试题)

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

DNS服务器在名称解析过程中正确的查询顺序为__________。(2011年上半年试题)

两个主机通过电缆直接相连，主机A的IP地址为220．17．33．24／28，而主机B的IP地址为220．17．33．100／28，两个主机互相ping不通，这时应该__________。(2013年上半年试题)

以太网的最大帧长为1518字节，每个数据帧前面有8个字节的前导字段，帧间隔为9．6us。快速以太网100BASE—T发送两帧之间的最大间隔时间约为(60)________________us。

生成树协议STP使用参数__________来选举根网桥。(2013年上半年试题)

有一种NAT。技术叫做“地址伪装(Masquerading)”，下面关于地址伪装的描述中正确的是__________。(2012年下半年试题)

工作站A的IP地址是202，117．17．24/28，而工作站B的IP地址是202．117．17．100/28，当两个工作站直接相连时不能通信，怎样修改地址才能使得这两个工作站可以互相通信？(56)。

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将__________。

我国现存最早的一部诊治杂病的专书是()

ApartfromBritain,theQueenisalsotheheadofstateofthefollowingcountriesEXCEPT______.()

_____的上层支付资金清算系统在整个支付系统中占据核心地位，其清算、结果处理中心集中管理各商业银行的清算账户，进行支付资金的最终清算。()

对于MS-DOS方式，按Alt+Enter键，可以在全屏幕和窗口方式之间切换，输入()命令可以退出“命令提示符”环境。

计算机有线网络目前通常采用的传输介质有()。

A．创伤性关节炎B．骨筋膜室综合征C．缺血性骨坏死D．损伤性骨化腕舟状骨骨折易造成

疾病的三间分布是指

设备监理实施细则的内容主要包括()。

在8086/8088汇编语言的伪操作命令定义：VAL　DB　2　DUP(1，2，3　DUP　(3)，2　DUP　(1，0))。则在VAL存储区内前十个字节单元的数据是(　　　)。

WhatistheaimofTheresaMay’splan?

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

软考中级

设信道带宽为3400Hz，调制为4种不同的码元，根据奈奎斯特定理，理想信道的数据速率为______。(2008年上半年试题)

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

DNS服务器在名称解析过程中正确的查询顺序为__________。(2011年上半年试题)

两个主机通过电缆直接相连，主机A的IP地址为220．17．33．24／28，而主机B的IP地址为220．17．33．100／28，两个主机互相ping不通，这时应该__________。(2013年上半年试题)

以太网的最大帧长为1518字节，每个数据帧前面有8个字节的前导字段，帧间隔为9．6us。快速以太网100BASE—T发送两帧之间的最大间隔时间约为(60)________________us。

生成树协议STP使用参数__________来选举根网桥。(2013年上半年试题)

有一种NAT。技术叫做“地址伪装(Masquerading)”，下面关于地址伪装的描述中正确的是__________。(2012年下半年试题)

工作站A的IP地址是202，117．17．24/28，而工作站B的IP地址是202．117．17．100/28，当两个工作站直接相连时不能通信，怎样修改地址才能使得这两个工作站可以互相通信？(56)。

计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若x的阶码大于y的阶码，则应将__________。

我国现存最早的一部诊治杂病的专书是()

ApartfromBritain,theQueenisalsotheheadofstateofthefollowingcountriesEXCEPT______.()

_____的上层支付资金清算系统在整个支付系统中占据核心地位，其清算、结果处理中心集中管理各商业银行的清算账户，进行支付资金的最终清算。()

对于MS-DOS方式，按Alt+Enter键，可以在全屏幕和窗口方式之间切换，输入()命令可以退出“命令提示符”环境。

计算机有线网络目前通常采用的传输介质有()。

A．创伤性关节炎B．骨筋膜室综合征C．缺血性骨坏死D．损伤性骨化腕舟状骨骨折易造成

疾病的三间分布是指

设备监理实施细则的内容主要包括()。

在8086/8088汇编语言的伪操作命令定义：VAL DB 2 DUP(1，2，3 DUP (3)，2 DUP (1，0))。则在VAL存储区内前十个字节单元的数据是( )。

WhatistheaimofTheresaMay’splan?

在8086/8088汇编语言的伪操作命令定义：VAL　DB　2　DUP(1，2，3　DUP　(3)，2　DUP　(1，0))。则在VAL存储区内前十个字节单元的数据是(　　　)。