答案及解析：[问答题]设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为{S1，S2，．．．，Sn}，且有si≤C(1≤i≤n)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。下面分别采用最先适

问题：

[问答题] 设有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]表示第i+1个集装箱当前已经装入货物的体积，下标从0开始i，j：循环变量k：所需的集装箱数min:当前所用的各集装箱装入了第i个货物后的最小剩余容量m:当前所需要的集装箱数temp：临时变量(2)函数firstfitint firstfit（　　）{inti，j；k=0：for(i=0；i＜n；i++){b[i]=0；}for（i=0；i＜n；i++）{(1)；while(C-b[j]＜s[i]){j++;}(2)；k=k>(j+1）k：(j+1)；}return k；}(3)函数bestfitint bestfit（　　）{int i，j，min，m，temp;k=0；for（i=0；i＜n；i++）{b[i]=0；}for(i=0；i＜n；i++）{min=C；m=k+1；for(j=0;j＜k+l；j++){temp=C-b[j]-s[i];if(temp>0&&temp＜min){(3)；m=j，}}(4)；k=k>(m+1）k:(m+1)；}return k；}【问题1】（8分）根据和【C代码】，填充C代码中的空(1)～(4)。【问题2】（4分）根据和【C代码】，该问题在最先适宜和最优适宜策略下分别采用了(5)和(6)算法设计策略，时间复杂度分别为(7)和(8)（用O符号表示）。【问题3】（3分）考虑实例n=10，C=10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11)（能或否）

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题