首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解0/1背包问题时,(26)能够确保获得最优解。用动态规划方求解O/1背包问题时,将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1,i,X)设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得
利用贪心法求解0/1背包问题时,(26)能够确保获得最优解。用动态规划方求解O/1背包问题时,将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1,i,X)设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得
admin
2019-03-11
83
问题
利用贪心法求解0/1背包问题时,(26)能够确保获得最优解。用动态规划方求解O/1背包问题时,将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1,i,X)设f
i
(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为W和p(j=1~n),则依次求解f0(X),f1(X),…,fn(X)的过程中使用的递推关系式为(27)。
选项
A、f
i
(X)=min{f
i
-1(X),f
i
-1(X)+P
i
}
B、f
i
(X)=max{f
i
-1(X),f
i
-1(X-W
i
)+P
i
}
C、f
i
(X)=min{f
i
-1(X-W
i
),f
i
-1(X-W
i
)+P
i
)
D、f
i
(X)=max{f
i
-1(x-W
i
),f
i
-1(X)+P
i
}
答案
B
解析
背包问题描述如下:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值和最大。0/1背包:对于每一种物品I装入背包只有一种选择,即要么装入要么不装入,不能装入多次或只装入部分。部分背包则是对于每一种物品I可以只装入部分。贪心法就是不求最优解,只求可行解的思想,只是局部最优,不考虑整体最优性。因此对于贪心法关键是贪心准则。对于0/1背包,贪心法之所以不一定得到最优解是因为它无法保证最终能将背包容量占满,背包空间的闲置使得背包所装物品的总价值降低了。动态规划法是将一个不容易解决的较大问题划分为若干个易于解决的小问题。
转载请注明原文地址:https://kaotiyun.com/show/tvRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
ICMP协议属于因特网中的(19)协议,ICMP协议数据单元封装在(20)中传送。(20)
ICMP协议属于因特网中的(19)协议,ICMP协议数据单元封装在(20)中传送。(19)
下面有关BGP4协议的描述中,不正确的是(26)。
所谓移动IP是指(58);实现移动IP的关键技术是(59)。(59)
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示路径中的分隔符,“/”在路径之首时表示根目录。图中,(1)。假设当前目录是A2,若进程A以如下两种方式打开文件f2:方式①fdl=open(“(2)/f2”,o_RlDON
按照IEEE802.1d协议,当交换机端口处于______状态时,既可以学习MAC帧中的源地址,又可以把接收到的MAC帧转发到适当的端口。
在检查网络故障时,要确定目标主机是否有故障,只需向同一网段中的其他主机发(1)命令,如果可达,则可以确定是目标主机发生了故障;否则,故障就可能是由(2)引起的。如果问题是由路由配置不当引起的,则使用Traceroute或Windows系统的(3)程序来跟踪
电话线路使用的带通滤波器的带宽为3kHz(300~3300Hz),根据奈奎斯特采样定理,最小采样频率应为(16)。
IEEEE802.11i标准制定的无线网络加密协议________________是一个基于________________算法的加密方案。
视频信息是连续的图像序列,(5)是构成视频信息的基本单元。
随机试题
将一叠文件分为若干组,每组正好有10份文件。已知其中2组文件中有18份通知。其余每组文件中最多有5份通知,且所有文件中通知占比正好为60%。那么这叠文件最多可能有多少份?
A.心率加快B.体循环静脉淤血C.毛细血管通透性增高D.肺淤血,肺水肿E.心室肥厚右心衰竭主要是由于()
以下关于共同海损陈述错误的是:
为使路面结构具备必须的抗疲劳、抗老化和抗变形累积的能力,必须满足()的要求。
工程产品质量缺陷,是指该工程产品没有满足()的要求。
云南白药药粉,含三七等中药原料,有止血、消炎等功效,5kg装
选举权和被选举权是我国人民参加国家管理,当家作主的具体表现。根据《中华人民共和国宪法》有关规定,以下享有选举权的我国公民是()。
YouhavedecidedtoquitthejobfromBDGroup,becauseyouwanttobaseyourcareersuccessonmorefrequentandhigh-qualityi
Wheredoesthisconversationtakeplace?
Theindustrialsocietieshavebeenextremelyproductiveduringthelasttwocenturies.The【S1】______advancehasbeenremarkabl
最新回复
(
0
)