首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
admin
2010-05-08
59
问题
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOuND(v,w,k,W)函数,其中v、w、k和w分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。下面给出0—1背包问题的回溯算法伪代码。
函数参数说明如下:w:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X)
1 cw←cp0
2 (1)
3 fp←l
4 while true
5 while k≤n and cw+w[k]≤w d。
6 (2)
7 cp←cp+v[k]
8 Y[k]←l
9 k←k+1
10 if k>n then
11 if fp
12 fp←cp
13 fw←cw
14 k←n
15 X←Y
16 else Y (k)←O
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠O and Y(k)≠l d0
19 (3)
20 if k=0 then return
2l Y[k]←0
22 cw←cw-w[k]
23 cp←cp-v[k]
24 (4)
考虑表6—1的实例,假设有3个物品,背包容量为22。图6—6中是根据上述算法构造的搜索树,其中结点的编号表示了搜索树生成的顺序,边上的数字I/O分别表示选择/不选择对应物品。除了根结点之外,每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值,右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解,应该选择物品 (5) ,获得的价值为 (6)。
对于表6—1的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为 (7) ,而用了上述回溯法,搜索树的结点数为 (8) .
选项
答案
(5)2与3(6) 35(7) 15(8) 8
解析
本题实质上是一个0-1背包问题,该问题最优化的目标函数是
max∑vixi (xi=0,1);
约束函数是:
∑pixi≤M (xi=0,1)。
0-1背包问题可用动态规划策略求得最优解,求解的递归式为
[*]
其中,nv
[j]表示由前i项物品组合且价格不超过i的背包的总价值。问题最终要求的背包的总价值为nv[n][M],根据上述递归式,可以很容易以自底向上的方式编写伪代码。
[问题1]中伪代码的第1行到第12行计算数组nv的元素值,第1行到第4行计算i为0或者j为0时nv
的值,对应递归式的第一种情况;第7行和第8行计算当j
[j]的值,对应递归式的第二种倩况;第9行到第12行对应递归式的第三种情况,故根据递归式,空(1)的答案为nv[i-1] [j];nv[i-1] [j-p
]+v
。伪代码的第13行到第19行求解哪些物品放入到背包中,物品项从后向前考虑,若nv
[j]:nv[i-1][j],表示物品mj没有放入背包中,即x
=0,故空(2)的答案为nv
[j]=nv[i-1][j]。相反,若物品mj放入背包中,则x
=l,同时背包还能选择不超过l-p
的价格的物品,故空(3)的答案为j=j-p
。
转载请注明原文地址:https://kaotiyun.com/show/jSDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
根据ANSI/IEEE829标准,(62)属于《测试案例说明》中的内容。 ①输入说明 ②测试目的 ③环境要求 ④特殊要求
内存按字节编址从A5000H到DCFFFH的区域其存储容量为()。
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
V模型是具有代表意义的测试模型,以下理解正确的是______。A.V模型认为测试阶段是与开发阶段并行的B.V模型是软件开发螺旋模型的变种,它反映了测试活动与分析和设计的关系C.V模型造成需求分析阶段隐藏的问题一直到后期的验收测试才被发现D.V模型是
按照开发阶段划分,软件测试可以分为______。①单元测试②集成测试③系统测试④确认测试⑤用户测试⑥验收测试⑦第三方测试
系统交付后,修改原来打印时总是遗漏最后一行记录的问题,该行为属于______维护。
软件测试使用各种术语描述软件出现的问题,以下叙述正确的是______。A.软件错误(error)是指在软件生命周期内的不希望或不可接受的人为错误,其结果是导致软件故障的产生B.软件缺陷(defect)是存在于软件(文档、数据、程序)之中的那些不希望或不
为检测系统所能承受的数据容量,应进行()。
已知关系模式:图书(图书编号,图书类型,图书名称,作者,出版社,出版日期,ISBN),图书编号唯一识别一本图书。建立“计算机”类图书的视图Compute-BOOK,并要求进行修改、插入操作时保证该视图只有计算机类的图书。CREATE(1)
随机试题
最常引起肝、脾、淋巴结肿大及中枢神经系统白血病的是()
患者,男性,15岁,癫痫大发作入院,医生请各科会诊该病例。该行为符合医德的哪项原则
猩红热的临床特点应除外
经纬仪有四条主要轴线,如果视准轴不垂直于横轴,此时望远镜绕横轴旋转时,则视准轴的轨迹是()。[2016年真题]
根据规定,下列有关各单位会计机构和会计业务设置的说法中,正确的有()。
按照投资基础的不同,下列选项中不属于现金流量表的是()。
提出“最近发展区”的教育家是()。
海伦.凯勒是举世______的作家和教育家。尽管命运之神夺走了她的视力和听力,这位女子却用勤奋和坚韧不拔的精神紧紧扼住了命运的喉咙。她的名字已经成为坚韧不拔意志的象征,传奇般的一生成为鼓舞人们战胜______的巨大精神力量。填入划横线部分最
国际经营战略[上海财经大学2015国际商务硕士]
Intheclassicmarriagevow(誓约),couplespromisetostaytogetherinsicknessandinhealth.Butanewstudyfindsthattheris
最新回复
(
0
)