首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解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
62
问题
利用贪心法求解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,将解答填入对应的解答栏内。某公司的分支机构通过一条DDN专线接入到公司总部,地址分配和拓扑结构如图5-1所示。在两台路由器之间可以使用静态路由,也可以使用动态路由。在[问题1]和[问题2]中,所使用的是静态路
阅读以下说明,回答问题1~4,将解答填入对应的解答栏内。利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。图4-1是在网络中划分VLAN的连接示意图。下面的命令是在交换机Switch1
阅读以下说明,回答问题1~6,将答案填入对应的解答栏内。某公司有一个局域网,在ISP申请了Internet接入,接入方式是以太网,ISP分配给了一个固定的IP地址为222.152.199.33、子网掩码为255.255.255.252、默认网关为2
该网络采用核心层、汇聚层、接入层的三层架构,所有计算机都采用静态IP地址。为了防止恶意用户盗用IP地址,网管员可采用(3)的策略来防止IP地址盗用,该策略应在三层架构中的(4)层实施。企业架设Web服务器对外进行公司及产品宣传,同时
阅读以下说明,根据要求回答问题。[说明]某公司网络结构如图1-23所示,通过在路由器上配置访问控制列表ACL来提高内部网络和Web服务器的安全。补充完成下面的ACL语句,禁止内网用户192.168.1.254访问公司web服务器和外网
活动目录(Active Directory)是由组织单元、域、(36)和域森林构成的层次结构,安装活动目录要求分区的文件系统为(37)。
关于在I/O设备与主机间交换数据的叙述,(4)是错误的。
DES加密算法采用的密码技术是(61),它采用(62)bit密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(63)加密技术,公钥密码是(64),常用的公钥加密算法有(65),它可以实现加密和数字签名。
RAID级别是指磁盘阵列中硬盘的组合方式,不同级别的RAID为用户提供的磁盘阵列在性能上和安全性的表现上也有不同。以下(31)是具有磁盘镜像和双工功能的磁盘阵列。
收到数据报时,如果本结点是路由结点,则需要(51)。
随机试题
培根认为,学问上的“装饰”的用途是指()
确诊二尖瓣狭窄最可靠的辅助检查方法是
A.骨盆骨折B.肱骨髁上骨折C.股骨颈骨折D.锁骨骨折E.Colles骨折易发生缺血性坏死的骨折
职业健康安全管理体系中的术语“不符合”是指任何与工作标准、惯例、法规、管理体系绩效等的偏离,其结果能直接导致( )。
某工业企业2018年8月转让一幢新建办公楼取得不含增值税收入4750万元,该办公楼建造成本和相关费用3700万元,缴纳与转让办公楼相关的除增值税之外的税金27.5万元(其中印花税金2.5万元)。该企业应缴纳土地增值税()万元。
从所给的四个选项中选择最合适的一个填入问号处,使之呈现一定的规律。
某市一栋大楼起火,导致11位正在施工的农民工遇难,20余农民工受伤。事故发生后,市政府依法组织有关部门成立事故调查组,对该起重大责任事故原因进行调查。经市政府批复后的事故调查报告认定:建设单位甲公司装修工程发包给乙公司后,乙公司又将装修工程违法分包给不具备
据调查,有1000位高考状元,但他们在以后的发展过程中都没有在从商、从政、教育科研方面成为顶级人才,你是怎么看的?
雍熙北伐
ThatcoldJanuarynight,IwasgrowingsickofmylifeinSanFrancisco.ThereIwas,walkinghomeatoneinthemorningaftera
最新回复
(
0
)