軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2022/1/24）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/1/24

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2022/1/24）

[試題4]

閱讀下列說明和C代碼，回答下列問題。

[說明]

設(shè)有n個(gè)貨物要裝入若干個(gè)容量為C的集裝箱以便運(yùn)輸，這n個(gè)貨物的體積分別為{s₁，s₂，...，s_n}，且有s₁≤c(1≤i≤n)。為節(jié)省運(yùn)輸成本，用盡可能少的集裝箱來裝運(yùn)這n個(gè)貨物。

下面分別采用最先適宜策略和最優(yōu)適宜策略來求解該問題。

最先適宜策略(firstfit)首先將所有的集裝箱初始化為空，對(duì)于所有貨物，按照所給的次序，每次將一個(gè)貨物裝入第一個(gè)能容納它的集裝箱中。

最優(yōu)適宜策略(bestfit)與最先適宜策略類似，不同的是，總是把貨物裝到能容納它且目前剩余容量最小的集裝箱，使得該箱子裝入貨物后閑置空間最小。

[C代碼]

下面是這兩個(gè)算法的C語言核心代碼。

11變量說明

n：貨物數(shù)

C：集裝箱容量

s：數(shù)組，長度為n，其中每個(gè)元素表示貨物的體積，下標(biāo)從0開始

B：數(shù)組，長度為n，b[i]表示第i+1個(gè)集裝箱當(dāng)前已經(jīng)裝入貨物的體積，下標(biāo)從0開始

i,j：循環(huán)變量

k：所需的集裝箱數(shù)

min：當(dāng)前所用的各集裝箱裝入了第i個(gè)貨物后的最小剩余容量

m：當(dāng)前所需要的集裝箱數(shù)

temp：臨時(shí)變量

12函數(shù)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函數(shù)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]

根據(jù)[說明]和[C代碼]，填充C代碼中的空缺處。

[問題2]

根據(jù)[說明]和[C代碼]，該問題在最先適宜和最優(yōu)適宜策略下分別采用了______和______算法設(shè)計(jì)策略，時(shí)間復(fù)雜度分別為______和______(用O符號(hào)表示)。

[問題3]

考慮實(shí)例n=10，C=10，各個(gè)貨物的體積為{4，2，7，3，5，4，2，3，6，2}。該實(shí)例在最先適宜和最優(yōu)適宜策略下所需的集裝箱數(shù)分別為______和______?？紤]一般的情況，這兩種求解策略能否確保得到最優(yōu)解?______(能或否)。