首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
admin
2010-05-08
51
问题
用回溯法求解此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
软件设计师下午应用技术考试
软考中级
相关试题推荐
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段,其中,___________并不是每个编译器都必需的。
《GB/T18905软件工程产品评价》中确定的通用评价过程包括四个方面,其中有关“规定评价”部分包含的内容有(67)。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。活动EH最多可以晚开始①天而不影响项目的进度。由于某种原因,现在需要同一个工作人员完成BC和BD,则完成该项目的最少时间为②天
标准符合性测试中的标准分类包括______。①数据内容类标准②通信协议类标准③开发接口类标准④信息编码类标准
按照开发阶段划分,软件测试可以分为______。①单元测试②集成测试③系统测试④确认测试⑤用户测试⑥验收测试⑦第三方测试
软件测试使用各种术语描述软件出现的问题,以下叙述正确的是______。A.软件错误(error)是指在软件生命周期内的不希望或不可接受的人为错误,其结果是导致软件故障的产生B.软件缺陷(defect)是存在于软件(文档、数据、程序)之中的那些不希望或不
在各种不同的软件需求中,()描述了产品必须要完成的任务,可以在用例模型中予以说明。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
黑盒测试法是根据产品的______来设计测试用例的。A.功能B.输入数据C.应用范围D.内部逻辑
网络测试类型包括________。①网络可靠性测试②网络可接受性测试③网络瓶颈测试④网络容量规划测试
随机试题
“二”和“两”在用法上有什么区别?
胸部高千伏摄影器件的选择,错误的是
A.葡萄胎B.胎动不安C.胎萎不长D.难免流产E.子宫发育不良淄体激素黄体酮适用于治疗
通常,掺有缓凝剂的混凝土浇水养护期不少于()。
1.背景某场道工程按工程量清单计价,得到如下数据:分部分项工程工程量清单计价合计1600万元,措施项目清单计价合计75万元,其他项目清单计价合计150万元,规费95万元,税率是不含税造价的3.4%。在工程进行中,按25%支付工程预付款,在未完施工尚需的
下列各项中,反映区域信贷资产质量水平在银行系统中所处的相对位置的指标是()。
根据税收征收管理法律制度的规定,因纳税人计算错误少缴税款,累计数额不足10万元的,税务机关在一定期限内可以追征税款和滞纳金,该一定期限是()。
挤出效应指在一个相对平稳的市场上,由于供应、需求有新的增加,导致部分资金从原来的预支中挤出,而流人到新的商品中。下列属于挤出效应的是()。
某市公安局针对电信诈骗,专门成立了反电信诈骗中心。依托反电信诈骗中心,仅一年,警方就为市民止损近20个亿。下列关于反电信诈骗中心以及警方可实施的防范电信诈骗举措的表述,正确的是()。
Jazzbeganintheearly20thcenturyasakindofmusicofblackAmericans.Itwas(36)______forsinging,fordancing,andfor
最新回复
(
0
)