首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
admin
2010-05-08
62
问题
用回溯法求解此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
软件设计师下午应用技术考试
软考中级
相关试题推荐
为了解系统在何种服务级别下会崩溃,应进行___________。
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段,其中,___________并不是每个编译器都必需的。
测试用例的三要素不包括________。
某指令流水线由5段组成,各段所需要的时间如下图所示。连续输入10条指令时的吞吐率为(6)。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。活动EH最多可以晚开始①天而不影响项目的进度。由于某种原因,现在需要同一个工作人员完成BC和BD,则完成该项目的最少时间为②天
一个程序的控制流图中有8个节点、12条边。在测试用例数最少的情况下,确保程序中每个可执行语句至少执行一次所需测试用例数的上限是________________。
软件测试信息流的输入包括______。①软件配置(包括软件开发文档、目标执行程序、数据结构)②开发工具(开发环境、数据库、中间件等)③测试配置(包括测试计划、测试用例、测试驱动程序等)④测试工具(为提高软件测试效率,使用测试
在Internet上有许多协议,下面的选项中能正确表示协议层次关系的是(12)。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
随机试题
Itisquitenecessaryforaqualifiedteachertohavegoodmannersand______(extension)knowledge.
急性腹膜炎最可靠的诊断依据是
丹毒的临床表现是( )疖的临床表现是( )
主要用于钢筋混凝土结构和预应力钢筋混凝土结构配筋的是()。
某企业去年的销售净利率为5.73%,资产周转率为2.17;今年的销售净利率为4.88%,资产周转率为2.88。若两年的资产负债率相同,今年的权益净利率比去年的变化趋势为( )。
运用存货模式确定现金最佳持有量时,其中的转换成本相当于存货管理中的()。
《中华人民共和国教师法》是由国家最高行政机关为提高教师队伍的素质而制定的。()
《劳动合同法》第96条规定:事业单位与实行聘用制的工作人员订立、履行、变更、解除或者终止劳动合同,法律、行政法规或者国务院另有规定的,依照其规定,未作规定的,依照本法有关规定执行。这一规则属于()。
科学发展观的核心是()。
Thechild’sabnormalbehaviorpuzzledthedoctor.
最新回复
(
0
)