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

admin2019-04-22 37

问题考虑下述背包问题的实例。有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://jikaoti.com/ti/qRf7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

有可能无限期拥有的知识产权是________________。

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

在BGP4协议中，(1)报文建立两个路由器之间的邻居关系，(2)报文给出了新的路由信息。(1)

某公司网络的地址是133．10．128．0／17，被划分成16个子网，下面的选项中不属于这16个子网的地址是__________。(2009年上半年试题)

与RIPv2相比，IGRP协议增加了一些新的特性，下面的描述中错误的是()。

若一个项目由9个主要任务构成，其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数，该项目的关键路径是(1)，完成项日所需的最短时间是(2)天。(2008年下半年试题)(2)

要进入以太端口配置模式，下面的路由器中命令，哪一条是正确的?(57)

某计算机系统由下图所示的部件构成，假定每个部件的千小时可靠度R均为0.9，则该系统的千小时可靠度约为(2)。

下面4种路由中，哪一种路由的子网掩码是255．255．255．255?_________。

进度安排的常用图形描述方法有Gantt图和PERT图。Gantt图不能清晰地描述(1)；PERT图可以给出哪些任务完成后才能开始另一些任务。下图所示的PERT图中，事件6的最晚开始时刻是(2)。(2010年上半年试题)(1)

植物的病原真菌与该种植物的种间关系是（）

A．呕吐伴腹痛、腹泻、发热B．呕吐伴眩晕，眼球震颤C．呕吐物有粪臭味伴腹痛、腹胀、不排便D．呕吐伴右上腹痛、发热、寒战、黄疸E．呕吐伴头痛，意识障碍，偏瘫急性胃肠炎

作为胃肠等手术前的清肠剂，宜选用

以质押方式申请担保流动资金贷款的，质押权利范围包括()等。

法院以盗窃罪判处被告人甲有期徒刑3年并处罚金2万元，甲以无钱为由拒不缴纳罚金。甲刑满释放后第5年为结婚购买了冰箱和彩电，法院得知上述情况后强行将冰箱和彩电扣押。法院的行为()。

TheprimarypurposeofthetextistoAccordingtotheorganizationofthetext,itmostlikelyappearedin

在设计表时，若输入掩码属性设置为"LLLL"，则能够接收的输入是(　　)。

一次，我去国外旅游，没想到有人用汉语对我说“你好”，他们都以为我是从中国来的。不是因为我长得像中国人，而是因为他们见到的中国客人更多。根据这段话，可以知道他：

TheEuropeanCentralBankleftitsmaininterestrateunchangedWednesday,choosingtoputtheonusonpoliticalleaderstoaddr

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

软考中级

有可能无限期拥有的知识产权是________________。

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

在BGP4协议中，(1)报文建立两个路由器之间的邻居关系，(2)报文给出了新的路由信息。(1)

某公司网络的地址是133．10．128．0／17，被划分成16个子网，下面的选项中不属于这16个子网的地址是__________。(2009年上半年试题)

与RIPv2相比，IGRP协议增加了一些新的特性，下面的描述中错误的是()。

若一个项目由9个主要任务构成，其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数，该项目的关键路径是(1)，完成项日所需的最短时间是(2)天。(2008年下半年试题)(2)

要进入以太端口配置模式，下面的路由器中命令，哪一条是正确的?(57)

某计算机系统由下图所示的部件构成，假定每个部件的千小时可靠度R均为0.9，则该系统的千小时可靠度约为(2)。

下面4种路由中，哪一种路由的子网掩码是255．255．255．255?_________。

进度安排的常用图形描述方法有Gantt图和PERT图。Gantt图不能清晰地描述(1)；PERT图可以给出哪些任务完成后才能开始另一些任务。下图所示的PERT图中，事件6的最晚开始时刻是(2)。(2010年上半年试题)(1)

植物的病原真菌与该种植物的种间关系是（）

A．呕吐伴腹痛、腹泻、发热B．呕吐伴眩晕，眼球震颤C．呕吐物有粪臭味伴腹痛、腹胀、不排便D．呕吐伴右上腹痛、发热、寒战、黄疸E．呕吐伴头痛，意识障碍，偏瘫急性胃肠炎

作为胃肠等手术前的清肠剂，宜选用

以质押方式申请担保流动资金贷款的，质押权利范围包括()等。

法院以盗窃罪判处被告人甲有期徒刑3年并处罚金2万元，甲以无钱为由拒不缴纳罚金。甲刑满释放后第5年为结婚购买了冰箱和彩电，法院得知上述情况后强行将冰箱和彩电扣押。法院的行为()。

TheprimarypurposeofthetextistoAccordingtotheorganizationofthetext,itmostlikelyappearedin

在设计表时，若输入掩码属性设置为"LLLL"，则能够接收的输入是( )。

一次，我去国外旅游，没想到有人用汉语对我说“你好”，他们都以为我是从中国来的。不是因为我长得像中国人，而是因为他们见到的中国客人更多。根据这段话，可以知道他：

TheEuropeanCentralBankleftitsmaininterestrateunchangedWednesday,choosingtoputtheonusonpoliticalleaderstoaddr

在设计表时，若输入掩码属性设置为"LLLL"，则能够接收的输入是(　　)。