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

admin2019-04-22 68

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

TCP使用3次握手协议建立连接，以防止；当请求方发出SYN连接请求后，等待对方回答以建立正确的连接：当出现错误连接时，响应。

编写汇编语言程序时，下列寄存器中，程序员可访问的是__________。(2010年下半年试题)

计算机系统的主存主要是由_____________构成的。

下图为DARPA提供的公共入侵检测框架示意图，该系统由四个模块组成，其中模块①～④对应的正确名称为__________。(2013年上半年试题)

利用三重DES进行加密，以下说法正确的是__________。(2013年上半年试题)

应该在(7)阶段制定系统测试计划。

采用CSMA／CD协议的基带总线，段长为1000m，数据速率为10Mb／s，信号传播速度为200m／μs则该网络上的最小帧长应为_____________比特。

下面的描述中，(3)不是RISC设计应遵循的设计原则。

在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet中，网络层的服务访问点是(21)。

文法G＝({E),{+,,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|EE|(E)|a。它生成由a,+,,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子aa+a，它的派生树是(

钢材的高温性能包括哪些?

简析《沙恭达罗》第四幕的艺术特色。

设函数f(x)在区间[0，4]上连续，而且∫1xf(t)dt=x2-，则f(2)=________.

其他药与之合用可使其吸收减少其他药与之合用可使其血药浓度降低

患儿8岁，患上呼吸道感染2周后，出现食欲减退、乏力、尿少、水肿。体温37．5℃、血压增高。尿蛋白、红细胞各(+)，补体C3低。诊断为急性肾小球肾炎。其首选的护理诊断／问题是

甲某于2007年3月20日取得一级建造师注册执业证书，由于工作单位变动，于2008年6月20日按规定办理了注册变更手续。根据有关规定，甲某的注册有效期应当截止到()。

行业分析历史资料研究法的资料来源包括(　　)。

导游人员要想提高自己的语言技能，平时应()

《中小学教师职业道德规范》规定的教师为人师表的内容可以概括为()

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

软考中级

TCP使用3次握手协议建立连接，以防止________________；当请求方发出SYN连接请求后，等待对方回答________________以建立正确的连接：当出现错误连接时，响应________________。

编写汇编语言程序时，下列寄存器中，程序员可访问的是__________。(2010年下半年试题)

计算机系统的主存主要是由_____________构成的。

下图为DARPA提供的公共入侵检测框架示意图，该系统由四个模块组成，其中模块①～④对应的正确名称为__________。(2013年上半年试题)

利用三重DES进行加密，以下说法正确的是__________。(2013年上半年试题)

应该在(7)阶段制定系统测试计划。

采用CSMA／CD协议的基带总线，段长为1000m，数据速率为10Mb／s，信号传播速度为200m／μs则该网络上的最小帧长应为_____________比特。

下面的描述中，(3)不是RISC设计应遵循的设计原则。

在OSI参考模型中，上层协议实体与下层协议实体之间的逻辑接口叫做服务访问点(SAP)。在Internet中，网络层的服务访问点是(21)。

文法G＝({E),{+,*,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子a*a+a，它的派生树是(

钢材的高温性能包括哪些?

简析《沙恭达罗》第四幕的艺术特色。

设函数f(x)在区间[0，4]上连续，而且∫1xf(t)dt=x2-，则f(2)=________.

其他药与之合用可使其吸收减少其他药与之合用可使其血药浓度降低

患儿8岁，患上呼吸道感染2周后，出现食欲减退、乏力、尿少、水肿。体温37．5℃、血压增高。尿蛋白、红细胞各(+)，补体C3低。诊断为急性肾小球肾炎。其首选的护理诊断／问题是

甲某于2007年3月20日取得一级建造师注册执业证书，由于工作单位变动，于2008年6月20日按规定办理了注册变更手续。根据有关规定，甲某的注册有效期应当截止到()。

行业分析历史资料研究法的资料来源包括( )。

导游人员要想提高自己的语言技能，平时应()

《中小学教师职业道德规范》规定的教师为人师表的内容可以概括为()

TCP使用3次握手协议建立连接，以防止；当请求方发出SYN连接请求后，等待对方回答以建立正确的连接：当出现错误连接时，响应。

文法G＝({E),{+,,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|EE|(E)|a。它生成由a,+,,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子aa+a，它的派生树是(

行业分析历史资料研究法的资料来源包括(　　)。