首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
用回溯法求解此0—1背包问题,请填充下面伪代码中(1)~(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为
admin
2010-05-08
50
问题
用回溯法求解此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
软件设计师下午应用技术考试
软考中级
相关试题推荐
假设某公司营销系统有营销点关系S(营销点,负责人姓名,联系方式)、商品关系P(商品名,条形码,型号,产地,数量,价格),其中,营销点唯一标识S中的每一个元组。每个营销点可以销售多种商品,每一种商品可以由不同的营销点销售。关系S和P的主键分别为(15),S
在统一建模语言(UML)中,描述系统与外部系统及用户之间交互的图是(8)。
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。活动EH最多可以晚开始①天而不影响项目的进度。由于某种原因,现在需要同一个工作人员完成BC和BD,则完成该项目的最少时间为②天
标准符合性测试中的标准分类包括______。①数据内容类标准②通信协议类标准③开发接口类标准④信息编码类标准
以下关于软件测试原则的叙述中,正确的是______。①所有软件测试都应追溯到用户需求②尽早地和不断地进行软件测试③完全测试是不可能的④测试无法发现软件潜在的缺陷⑤需要充分注意测试中的群集现象
假设关系R1和R2如下图所示:若进行R1R2运算,则结果集分别为(1)元关系,共有(2)个元组。(2)
网络测试类型包括________。①网络可靠性测试②网络可接受性测试③网络瓶颈测试④网络容量规划测试
随机试题
心肌不会产生强直收缩,其原因是
下列哪项Coombs试验阴性
取某药2g,精密称定的称量范围为
张某与某建筑公司签订了一份为期3年的劳动合同并约定了1个月的试用期,试用期间张某的工资不得低于本单位相同岗位最低档工资或者劳动合同约定工资的(),并不得低于用人单位所在地的最低工资标准。
甲公司评估基准日为2016年1月1日,基准日投入资本1200万元,预计2017—2020年投入资本为1560万元、1950万元、2340万元、2574万元,此后每年投入的增长率为5%,投入资本报酬率为14%,无风险报酬率3%,市场平均报酬率为8%,公司的β
如果企业在发行债券的契约中规定了允许提前偿还的条款,则当预测年利息率下降时,一般应提前赎回债券。()
()不符合心理咨询的唯物主义观点。
Accordingtotheauthor,thereisatrend______.Theword"entitlement"inthetext(Para.3)probablymeans______.
Japanhasalongtradingtradition.Australiaisoneofthebiggestwinnersfromglobalization.
UniversalHealthCoverageVocabularyandExpressionsuniversalhealthcoveragepeople-centredcareintegratedservicedel
最新回复
(
0
)