首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解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
84
问题
利用贪心法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
IEEE802.11i所采用的加密算法为______。
网络设计过程包括逻辑网络设计和物理网络设计两个阶段,各个阶段都要产生相应的文档,以下选项中,(1)属于逻辑网络设计文档,(2)属于物理网络设计文档。(20l1年下半年试题)(1)
DNS服务器中的资源记录分成不同类型,其中指明区域主服务器和管理员邮件地址的是(51),指明区域邮件服务器地址的是(52)。(52)
在CPU中用于跟踪指令地址的寄存器是__________。(2011年上半年试题)
公钥体系中,用户甲发送给用户乙的数据要用______进行加密。
数据流图(DFD)对系统的功能和功能之间的数据流进行建模,其中顶层数据流图描述了系统的____________。
在某公司局域网中的一台Windows主机中,先运行(47)命令,再运行“arp-a”命令,系统显示的信息如下图所示。
某网络拓扑如下图所示。要得到如下所示的输出信息,应在设备(1)上执行(2)命令。(1)应填_________。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为(4)天。活动BD和HK最早可以从第(5)天开始。(活动AB、AE和AC最早从第1天开始)(5)
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某会议中心提供举办会议的场地设施和各种设备,供公司与各类组织机构租用。场地包括一个大型报告厅、一个小型报告厅以及诸多会议室。这些报告厅和会议室可提供的设备有投影仪、白板、视频播放
随机试题
1822年,英国人巴贝奇首先提出来整个计算过程自动化的概念,设计出了第一台通用自动时序控制机械式计算机,称为________。
为观察肾的分泌排泄功能应做的检查是( )
预防HBeAg阳性母亲所生的新生儿HBV感染最有效的措施是
下列哪种情况在发生垂体危象时最为多见
据统计报载:截至到2001年年底,某市有高科技园区3个,已征土地6325hm2,占该市各类开发区已征土地总面积的18%。该城市在2002年年初,为了合理的利用已征土地,综合制定了科学的规划布局方案,将废弃的小型工场、市场等以及公共设施进行了重新布置,对城
工程项目质量控制系统的构成,依控制内容划分不正确的为()。
年化收益率有______与______之分。( )
对幼儿园活动的正确理解是()。
Studythedrawingcarefullyandwriteanessayof160-200words.Youshould1)describethedrawingbriefly,2)interpretthe
A、Sheagreeswithdieting.B、Sheopposesdieting.C、Shenevercaresaboutdieting.D、Shehasbeenonadiet.B信息明示题。对话一开始,男士询问女士
最新回复
(
0
)