首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
admin
2010-05-08
60
问题
用回溯法求解此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
软件设计师下午应用技术考试
软考中级
相关试题推荐
某企业研发信息系统的过程中,______不属于数据库管理员(DBA)的职责。
内存按字节编址从A5000H到DCFFFH的区域其存储容量为()。
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户的服务要求。这种行为属于____________维护。
测试过程中,正确的测试顺序应该是()。①单元测试②集成测试③系统测试
某指令流水线由5段组成,各段所需要的时间如下图所示。连续输入10条指令时的吞吐率为(6)。
以下关于防火墙功能特性的说法中,错误的是______。
Bug记录信息包括________________。①被测软件名称②被测软件版本③测试人④错误等级⑤开发人⑥详细步骤
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
测试记录包括、(64)。①测试计划或包含测试用例的测试规格说明。②测试期间出现问题的评估与分析。③与测试用例相关的所有结果,包括在测试期间出现的所有失败。④测试中涉及的人员身份。
随机试题
调查研究的重要原则“调查的面要宽,调查所获取的信息要广”,适用的企业会计制度设计方案是()
患者,女性,45岁。因劳累性心慌气急3个月入院。体检:心尖部闻及舒张期隆隆样杂音和开瓣音。超声心动图提示二尖瓣瓣膜轻度增厚,瓣口面积0.8cm2,腱索稍增粗,其他瓣膜正常。本患者最佳的治疗方案是
患者,女,42岁,因骨盆骨折,肝破裂,失血性休克入院,治疗中出现呼吸加快,呼吸窘迫,口唇发绀,双肺闻及湿啰音,PaO2<8.0kPa。有效处理为()。
治疗虚劳脾胃阴虚者,应首选
关于《建设项目环境影响评价资质管理办法》,下列说法错误的是()。
已知某企业人力资源供给情况如下表,期初人员数量:高层领导30人、部门领导70人、业务主管120人、业务员180人。下一年预计部门领导将减少()人。
某公司的境外子公司的记账本位币为美元。本期期未汇率为1美元=6.40元人民币,当期即期汇率近似汇率(采用平均汇率确定)为1美元=6.50元人民币。子公司资产负债表中“盈余公积”项目年初余额为200万美元,折合人民币1320万元,奉期所有者权益变动表“提取盈
己公司是一家饮料生产商,公司相关资料如下:资料一:己公司2015年相关财务数据如表1所示。假设己公司成本性态不变,现有债务利息水平不表。资料二:己公司计划2016年推出一款新型饮料,年初需要购置一条新生产线,并立即投入使用。该生产线购置价格为500
水泥:建房
A、标点错误B、语法问题C、语言风格D、文章结构A
最新回复
(
0
)