首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解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
81
问题
利用贪心法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
关于链路状态协议与距离矢量协议的区别,以下说法中错误的是(25)。
IPv6的可聚合全球单播地址前缀为(59),任意播地址的组成是(60)。(60)
在异步通信中,每个字符包括1位起始位、7位数据位、1位奇偶校验位和1位终止位,每秒钟传送100个字符,则有效数据速率为__________。(2008年下半年试题)
操作系统是裸机上的第一层软件,其他系统软件(如(1)等)和应用软件都是建立在操作系统基础上的。下图①、②、③分别表示(2)。(2009年下半年试题)(1)
与算术表达式“(a+(b—c))*d”对应的树是(7)。
结构化综合布线系统分为六个子系统,其中水平子系统的作用是(67),干线子系统的作用是(68)。(68)
边界网关协议BGP的报文(22)传送。一个外部路由器通过发送(23)报文与另一个外部路由器建立邻居关系,如果得到应答,才能周期性地交换路由信息。(23)
在BGP4协议中,(1)报文建立两个路由器之间的邻居关系,(2)报文给出了新的路由信息。(2)
阅读以下说明和流程图,从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像,以:“1”表示黑像素点,以“0”表示白像素点。图像二元树结构表示
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某会议中心提供举办会议的场地设施和各种设备,供公司与各类组织机构租用。场地包括一个大型报告厅、一个小型报告厅以及诸多会议室。这些报告厅和会议室可提供的设备有投影仪、白板、视频播放
随机试题
《周礼.地官.遂人》把大小不同的道路分为五等,从小到大排列正确的是_______________。
患者,年轻男性,近年来反复咳嗽伴有脓痰,有时痰中带血,无吸烟史及其他不良嗜好。查体:双下肺呼吸音增粗,痰检未见杆菌。该患者最有可能的诊断是
对水泥胶砂强度试验结果带来一些影响的试验条件是()。
擅自设立金融机构罪,是指未经国家有关主管部门批准,擅自设立()的行为。
下列关于PowerPoint的叙述,错误的是()。
定义在R上的偶函数f(x)的部分图像如图所示,则在(-2,0)上,下列函数中与f(x)的单调性不同的是()。
一、注意事项1.本试卷由给定资料与作答要求两部分构成。2.第一题、第二题、第五题,所有考生都必须作答。第三题仅限行政执法类、市(地)以下综合管理类职位的考生作答。第四题仅限考省级(含副省级)以上综合管理类职位的考生作答
一、注意事项1.本题本由给定资料与申论要求两部分构成。考试时限为150分钟。其中,阅读给定资料参考时限为40分钟,作答参考时限为110分钟。2.监考人员宣布考试开始时,你才可以开始答题。3.所有题目一律使用现代汉语作答在指定位置。
某软件项目的活动图如图4-3所示。图中顶点表示项目里程碑,连接顶点的边表示包含的活动,则该活动图的关键路径是(1),活动FG的松弛时间为(2)。(2)
Backin【B1】______,civilwarbrokeoutinBurundi.Manywerekilledina【B2】______ofinter-ethnicviolence.Thismonth,Bur
最新回复
(
0
)