软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2022/9/26）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2022/9/26

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2022/9/26）

[试题4]

阅读下列说明和C代码，回答下列问题。

[说明]

设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为{s₁，s₂，...，s_n}，且有s₁≤c(1≤i≤n)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。

下面分别采用最先适宜策略和最优适宜策略来求解该问题。

最先适宜策略(firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。

最优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。

[C代码]

下面是这两个算法的C语言核心代码。

11变量说明

n：货物数

C：集装箱容量

s：数组，长度为n，其中每个元素表示货物的体积，下标从0开始

B：数组，长度为n，b[i]表示第i+1个集装箱当前已经装入货物的体积，下标从0开始

i,j：循环变量

k：所需的集装箱数

min：当前所用的各集装箱装入了第i个货物后的最小剩余容量

m：当前所需要的集装箱数

temp：临时变量

12函数firstfit

int firstfit13 {

int i, j;

k=0;

for(i=0; i＜n;i++){

b[i]=0;

}

for i=0; i＜n;i++) {

______;

while (C-b [j]＜s [i]){

j++;

}

______;

k=k＞(j+1)?k: (j+1);

}

return k;

}

14函数bestfit

int bestfit13 {

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+1;j++) {

temp=C-b [j]-s [i];

if(temp＞0 && temp＜min){

______;

m=j;

}

}

______;

k=k＞(m+1)?k: (m+1);

}

return k;

}

[问题1]

根据[说明]和[C代码]，填充C代码中的空缺处。

[问题2]

根据[说明]和[C代码]，该问题在最先适宜和最优适宜策略下分别采用了______和______算法设计策略，时间复杂度分别为______和______(用O符号表示)。

[问题3]

考虑实例n=10，C=10，各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为______和______。考虑一般的情况，这两种求解策略能否确保得到最优解?______(能或否)。