阅读下列说明,回答问题1至问题2,将解答填入答题纸的对应栏内。 【说明】 0—1背包问题可以描述为:
阅读下列说明,回答问题1至问题2,将解答填入答题纸的对应栏内。
【说明】
0—1背包问题可以描述为:有n个物品,对i=l,2,…,n,第i个物品价值为vi,重量为wi(vi和wi为非负数),背包容量为w(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,即,且总重量不超过背包容量,即
,其中,xi∈{O,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品放入背包。
用回溯法求解此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<cp then
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)
(1)k←1(2)cw←cw+w[k](3)k←k-1(4)k←k+l
阅读下列说明,回答问题 1 至问题 7,将解答写在答题纸的对应栏内。 【说明】 扫描技术是网络攻防的 计算机类考试 2020-05-26 …
阅读下列说明和E-R图,回答问题1至问题3,将解答填入对应栏内。 [说明] 某学校的教学系统描述如下 计算机类考试 2020-05-26 …
阅读下列说明,回答问题1至问题2,将解答填入答题纸的对应栏内。 【说明】 0—1背包问题可以描述为: 计算机类考试 2020-05-26 …
阅读以下说明和表,回答问题1~4问题。 [说明] 一个描述学校的部分关系模式的结果描述如下: 1.一 计算机类考试 2020-05-26 …
阅读以下说明和流程图,回答问题1至问题3,将解答写在对应栏内。 【说明】 (1)流程图描述某大型商店 计算机类考试 2020-05-26 …
阅读以下说明和流程图,回答问题1至问题3,将答案写在对应栏内。【说明】 流程图描述了某高校图书订购 计算机类考试 2020-05-26 …
阅读下列说明和流程图,回答问题1至问题3,将解答写在对应栏内。 【说明】 流程图描述了某宽带数据专 计算机类考试 2020-05-26 …
如图描述了秦宁放学回家的行程情况.根据上图回答问题:(1)秦宁放学后是径直回家吗?(2)图中的哪一 其他 2020-07-03 …
读下列图文资料回答问题.(1)根据材料从地质构造的角度描述宁夏平原的成因.(2)说明图中AB所在地区 其他 2020-11-08 …
文学家陶渊明在《桃花源记》中描述的“世外桃源”是这样的:“土地平旷,屋舍俨然,有良田美池桑竹之属.阡 其他 2020-12-18 …