首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解0/1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设fi(x)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包
利用贪心法求解0/1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设fi(x)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包
admin
2008-01-15
45
问题
利用贪心法求解0/1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设fi(x)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为 wj和pj(j=1~n)。则依次求解f0(x)、f1(x)、...、fn(X)的过程中使用的递推关系式为(56)。.
选项
A、优先选取重量最小的物品
B、优先选取效益最大的物品
C、优先选取单位重量效益最大的物品
D、没有任何准则
答案
D
解析
本题考查0/1背包问题的动态规划求解方法。
利用贪心法可以解决普通背包问题(即允许将物品的一部分装入背包),此时使用“优先选取单位重量效益最大的物品”的量度标准可以获得问题最优解,但是贪心法不能用来求解0/1背包问题,题目中供选择的A、B、C三种量度标准均不能确保获得最优解。
利用动态规划求解0/1背包问题时,按照题目中约定的记号。KNAP(1,i,X)的最优解来自且仅来自于以下两种情况之一:
. 第i个物品不装入背包,此时最优解的值就是子问题KNAP(1,i-1,X)的最优解的效益值,即为fi-1(X);
. 第i个物品装入背包,此时最优解的值为第i个物品的效益值与子问题 KNAP(1,i-1,X-wi)的最优解效益值之和,即为fi-1(X-wi)+pi。
综上,KNAP(1,i,X)最优解的值为以上两种情况中效益值更大者,即取max。
转载请注明原文地址:https://kaotiyun.com/show/QbxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。某公司由总部和分支机构构成,通过IPSec实现网络安全,网络拓扑结构如图4-1所示。路由器之间的地址分配如表4-1所示。IPSec是IETE以RFC)侈式公布的一组
阅读以下说明,回答问题1~5,将答案填入对应的解答栏内。配置WWW服务器是Linux操作平台的重要工作之一,而Apach是目前应用最为广泛的Web服务器产品之一。在Linux下安装ApacheWeb服务,Apache服务程序http启动时需要读取
阅读以下说明,回答问题1~5,将解答填入对应的解答栏内。在图4-1所示的网络中,运行的路由协议是OSPF,有0、1和2三个区域,其中Router1的S0端口、Router2的S0端口属于区域0,Router1的E0端口、Router3的E0端口属于区
阅读以下说明,回答问题1~4,将答案填入对应的解答栏内。最佳管理的园区网通常是按照分级模型来设计的。在分级设计模型中,通常把网络设计分为3层,即核心层、汇聚层和接入层。图1-1所示的是某公司的网络拓扑图,但该公司采用的是紧缩核心模型,即将核心层和
在“本地安全设置”中,用户账户锁定策略如图4-2所示,当3次无效登录后,用户账户被锁定的实际时间是(2)。如果“账户锁定时间”设置为0,其含义为(3)。备选答案:A.账户将一直被锁定,直到管理员明确解除对它的锁定B.账户将被
该网络采用核心层、汇聚层、接入层的三层架构。根据层次化网络设计的原则,数据包过滤、协议转换应在(11)层完成;(12)层提供高速骨=F线路;MAC层过滤和IP地址绑定在(13)层完成。(12)
IPSec安全体系结构包括AH,ESP和ISAKMP/Oakley等协议。其中,(4)为IP包提供信息源验证和报文完整性验证,但不支持加密服务;(5)提供加密服务;(6)提供密钥管理服务。(4)
在Linux系统中,DNS查询文件内容如下所示,该文件的默认存储位置为(5),当用户做DNS查询时,首选DNS服务器的IP地址为(6)。Serachdomain.test.cnNameserver210.34.0.14
在RAS上存在着两个RJ45的端口,分别为Console与AUX,请问这两个端口的用途是什么?(控制在100个字以内)在调用超级终端程序进行设备连接时,应该对设备的连接参数进行正确设置,参数主要包括串口数据传输率、数据位数。停止位数以及是否有奇偶校验。
阅读以下说明,回答问题,将解答填入答题纸对应的解答栏内。【说明】图2-1为某公司数据中心拓扑图,两台存储设备用于存储关系型数据库的结构化数据和文档、音视频等非结构化文档,规划采用的RAID组合方式如图2-2、图2-3所示。图2-2所示的RAID方
随机试题
若正项级数收敛,则级数________.
A.猪链球菌B.大肠杆菌C.沙门氏菌D.多杀性巴氏杆菌E.副猪嗜血杆菌能够引起禽类肺炎、气囊炎、心包炎、腹膜炎、输卵管炎,麦康康培养基菌落为红色的病原是()。
已知甲、乙为两个寿命期相同的互斥项目,通过测算得出:甲、乙两项目的内部收益率分别为18%和14%,甲、乙两项目的净现值分别分为240万元和320万元。假如基准收益率为12%,则以下说法中正确的是()。
被评估A设备为2000年从德国引进的设备,进口合同中的FOB价是20万马克。2005年10月进行评估时德国厂家已不再生产A设备了,其替代产品B的FOB报价为35万马克。按照通常情况,设备的实际成交价应为报价的90%,境外运杂费约占FOB价格的5%,保险费约
某企业生产甲产品,实际产量为9600件,实际工时为17280小时,实际变动制造费用与固定制造费用分别为88128元和200000元。本月预算产量为8000件,单位工时标准为1.6小时/件,标准变动制造费用分配率为4元/小时,标准固定制造费用分配率为6.4元
以下各组植物中,属于木本植物的是()。
a>2,则双曲线的离心率的取值范围是()。
在等比数列{an}中,,则首项a1为()
三舍法
一个工作人员可使用多台计算机,而一台计算机被多个人使用,则实体工作人员与实体计算机之间的联系是
最新回复
(
0
)