首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解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
82
问题
利用贪心法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
下面的OSPF网络由多个区域组成。在这些路由器中,属于主干路由器的是(1),属于自治系统边界路由器(ASBR)的是(2)。(1)
城域以太网在各个用户以太网之间建立多点第二层连接,IEEE802.1ad定义的运营商网桥协议提供的基本技术是在以太帧中插入(26)字段,这种技术被称为(27)技术。(27)
TCP/IP网络中最早使用的动态路由协议是(21)协议,这种协议基于(22)算法来计算路由。(22)
DMA工作方式下,在____________之间建立直接的数据通信。
包过滤防火墙通过(45)来确定数据包是否能通过。
TCP协议使用(63)次握手过程建立连接,这种方法可以防止(64)。TCP使用的流量控制协议是(65)。(65)
以下加密算法中,适合对大量的明文消息进行加密传输的是__________。
在Internet上有许多协议,下面的选项中能正确表示协议层次关系的是(23)。
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某会议中心提供举办会议的场地设施和各种设备,供公司与各类组织机构租用。场地包括一个大型报告厅、一个小型报告厅以及诸多会议室。这些报告厅和会议室可提供的设备有投影仪、白板、视频播放
随机试题
A、干扰素B、环孢素C、转移因子D、糖皮质激素E、环磷酰胺小剂量抑制体液免疫,大剂量抑制细胞免疫的是
在充分满足油井生产能力需求的前提下,应尽量使用()。冲程加大,可以增加排量,降低动液面,提高油井产量;同时,可减少气体对泵的影响,提高抽汲效率。
IcanclearlyrememberthefirsttimeImetMr.Andrews,myoldheadmaster,【21】thatwasovertwentyyearsago.Duringthewar,I
在以下对乳剂的叙述中,正确的是
根据《国务院关于投资体制改革的决定》,实行备案制的企业投资项目,一般由企业按属地原则向地方政府()备案。
下列关于战略变革的发展阶段的说法中,正确的有()。
下列传统节日中,未作为全国性法定节日的是()。
访谈法最适合了解外显行为,而通过外显行为,可以发现行为背后的原因。()
________DavidsayssoundsrighttoHelen.That’swhyshehadmadeuphermindnottoleavehim________happens.
Bettingagainstanindustrywithaddictsforcustomerscarriesobviousrisks.【C1】______theseareuncertaintimesforBigTobacco
最新回复
(
0
)