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

admin2019-04-22 44

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

(2)

选项 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/14RZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)，则完成该项目的最少时间为天。活动FG的松弛时间为天。

在RAID技术中，同一RAID组内允许任意两块硬盘同时出现故障仍然可以保证数据有效的是()。

下图1所示内容是在图2中的(27)设备上执行(28)命令查看到的信息片段。该信息片段中参数(29)的值反映邻居状态是否正常。(29)

下列说法错误的是__________。

在Linux系统中可用ls-al命令列出文件列表，__________列出的是一个符号连接文件。(2010年下半年试题)

下面关于交换机的说法中，正确的是______。

选择软件开发工具时，应考虑功能、(5)，稳健性、硬件要求和性能、服务和支持。

下列叙述中错误的是__________。

根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。对于表2-1、表2-2所示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么?

胎盘剥离征象的表现为

下列对生物资产的税务处理不正确的有()。

在注册会计师审计发展过程中。标志着注册会计师职业诞生的是()。

教师职业道德的核心和精髓是()。

有教师表(教师号，教师名，职称，基本工资)，其中基本工资的取值与教师职称有关，实现这个约束的可行方案是()。

在窗体画一名为CommonDialogl，则下列与CommonDialogl．ShowOpen方法等效的语句是

Thegreatchariotofsociety,whichforsolonghadrundownthegentleslopeoftradition,nowfounditselfpoweredbyaninter

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

软考中级

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)，则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。

在RAID技术中，同一RAID组内允许任意两块硬盘同时出现故障仍然可以保证数据有效的是()。

下图1所示内容是在图2中的(27)设备上执行(28)命令查看到的信息片段。该信息片段中参数(29)的值反映邻居状态是否正常。(29)

下列说法错误的是__________。

在Linux系统中可用ls-al命令列出文件列表，__________列出的是一个符号连接文件。(2010年下半年试题)

下面关于交换机的说法中，正确的是______。

选择软件开发工具时，应考虑功能、(5)，稳健性、硬件要求和性能、服务和支持。

下列叙述中错误的是__________。

根据上述说明，请给出(1)“职员”关系模式的主键和外键。(2)“部门”关系模式的主键和外键。对于表2-1、表2-2所示的“职员”和“部门”关系，请指出下列各行是否可以插入“职员”关系，为什么?

胎盘剥离征象的表现为

下列对生物资产的税务处理不正确的有()。

在注册会计师审计发展过程中。标志着注册会计师职业诞生的是()。

教师职业道德的核心和精髓是()。

有教师表(教师号，教师名，职称，基本工资)，其中基本工资的取值与教师职称有关，实现这个约束的可行方案是()。

在窗体画一名为CommonDialogl，则下列与CommonDialogl．ShowOpen方法等效的语句是

Thegreatchariotofsociety,whichforsolonghadrundownthegentleslopeoftradition,nowfounditselfpoweredbyaninter

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)，则完成该项目的最少时间为天。活动FG的松弛时间为天。