阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn],且有si≤C(1≤i≤n)。为节省运输成本,用尽可能少的集装箱来装运这n个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略(firstfit)首先将所有的集装箱初始化为空,对于所有货物,按照所给的次序,每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(bestfit)与最先适宜策略类似,不同的是,总是把货物装到能容纳它且目前剩余容重最小的集装箱,使得该箱子装入货物后闲置空间最小。 【C代码】
下面是这两个算法的C语言核心代码。
(1)变量说明
n:货物数
C:集装箱容量
s:数组,长度为n,其中每个元素表示货物的体积,下标从0开始。
b:数组,长度为n,b[i]表示第n+i个集装箱当前已经装入货物的体积,下标从0开始
i,j:循环变量
k:所需的集装箱数
min:当前所用的各集装箱装入了第i个货物后的最小剩余容量
m:当前所需的集装箱数
temp:临时变量
(2)函数firstfit
intfirs七fit()(
inti,j;
k=0; for(i=0;i b[i]=0;
}
for(i=0;i (1);
while(C—b[j] j++;
}
(2);
k=k>(j+1)?k:(j+1);
}
returnk;
}
(3)函数bestfit
intbestfit(){
inti,j,min,m,temp;
k=0;
for(i=0;i b[i]=0;
}
for(i=0;i min=C;
m=k+1:
for(j=0;j temp=c—b[j]一s[i];
if(temp>O&&temp (3);
m=j;
}
}
(4) ;
k=k>(j+1)?k:(j+1);
}
return k;
}
问答题 根据【说明】和【C代码】,填充C代码中的空(1)~(4)。
【正确答案】正确答案:(1)j=0 (2)b[j]=b[j]+s[i] (3)min=temp (4)b[m]=b[m+s[i]
【答案解析】解析:本题描述的算法包括最先适宜算法和最优适宜算法。其中,最先适宜算法要求按顺序给货物找到一个能容纳它的集装箱,找到即可装箱。这里的关键在于找到第一个能容纳它的集装箱,从头到尾遍历各集装箱即可。firstfit函数用于实现最先适宜算法。定位到空(1)处,其上面的for循环用于对所有n个货物进行遍历,分别找出满足条件c-b啪>=s[i]的集装箱。但条件c-b[j]
问答题 根据【说明】和【C代码】,该问题在最先适宜和最优适宜策略下分别采用了(5)和(6)算法设计策略,时间复杂度分别为(2)和(8)(用O符号表示)。
【正确答案】正确答案:(5)贪心 (6)贪心 (7)O(n2) (8)O(n2)
【答案解析】解析:贪心算法在解决最优化问题上是仅根据当前已有的信息作出选择,即不是从整体最优考虑,它所作出的选择只是力求局部最优。最先适宜策略和最优适宜策略均采用了该算法设计策略。对于时间复杂度,应根据程序中循环的层数及每层循环的次数来进行计算。可以很容易地判断,这两种算法的时间复杂度均为O(n 2 )。
问答题 考虑实例n=10,C=10,各个货物的体积为{4,2,7,3,5,4,2,3,6,2}。该实例在最先适宜和最优适宜策略下所需的集装箱分别为(9)和(10)。考虑一般的情况,这两种求解策略能否确保得到最优解? (11)(能或否)
【正确答案】正确答案:(9)5 (10)4 (11)否
【答案解析】解析:本问题考查对程序的具体理解和应用。对firstfit函数进行遍历的结果如下: