2. 计算机
  3. 用回溯法求解此0—1背包问题，请填充下面伪代码中(1)～(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为

用回溯法求解此0—1背包问题，请填充下面伪代码中(1)～(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为

admin2010-05-08  59
问题 用回溯法求解此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 fp12    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

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)