中级软件设计师填空集试卷（中级软件设计师）_4.docVIP

试卷第 PAGE 1 页共 NUMPAGES 4 页 中级软件设计师填空集试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、阅读下列说明，回答问题1和问题2，将解答填入对应栏内。[说明]0-1背包问题可以描述为：有n个物品，i=1，2，…，n，第i个物品价值为vi，重量为wi(vi和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。[问题1]用回溯法求解此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←cp←02 (1)3 fp←-14 While true5 while k≤n and cw+w[k]≤W do6 (2)7 cp←cp+v[k]8 Y[k]←19 k←k+110 if k＞n then11 if fp＜cp then12 fp←cp13 fw←cw14 k←n15 X←Y16 else Y(k)←017 while BOUND(cp，cw，k，W)≤fp do18 while k≠0 and Y(k)≠1 do19 (3)20 if k=0 then return21 Y[k]←022 cw←cw←w[k]23 cp←cp←v[k]24 (4)[问题2]考虑表21-3所示的实例，假设有3个物品，背包容量为22。图21-12是根据上述算法构造的有哪些信誉好的足球投注网站树，其中结点的编号表示有哪些信誉好的足球投注网站树生成的顺序，边上的数字I/O分别表示选择/不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。对于表21-3所示的实例，若采用穷举法有哪些信誉好的足球投注网站整个解空间，则有哪些信誉好的足球投注网站树的结点数为 (7) ；而采用上述的回溯法，有哪些信誉好的足球投注网站树的结点数为 (8) 。（1）处填（ ）。 2、阅读下列说明，回答问题1和问题2，将解答填入对应栏内。[说明]0-1背包问题可以描述为：有n个物品，i=1，2，…，n，第i个物品价值为vi，重量为wi(vi和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。[问题1]用回溯法求解此0-1背包问题，请填充伪代码中的空缺(1)～(4)。回溯法是一种系统的有哪些信誉好的足球投注网站方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，有哪些信誉好的足球投注网站满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的有哪些信誉好的足球投注网站效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v，w，k，w)函数，其中v、w、k和W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于有哪些信誉好的足球投注网站树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无须再扩展。下面给出0-1背包问题的回溯算法伪代码。函数参数说明如下：W：背