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

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

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

點擊查看：更多軟件設(shè)計師習題與指導

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2021/12/23）

試題四
閱讀下列說明和C代碼，將應填入  (n)  處的字句。
[說明]
設(shè)某一機器由n個部件組成，每一個部件都可以從m個不同的供應商處購得。供應商j供應的部件i具有重量wij和價格cij。設(shè)計一個算法，求解總價格不超過上限cc的最小重量的機器組成。
采用回溯法來求解該問題：
首先定義解空間。解空間由長度為n的向量組成，其中每個分量取值來自集合{1，2，…，m)，將解空間用樹形結(jié)構(gòu)表示。
接著從根結(jié)點開始，以深度優(yōu)先的方式搜索整個解空間。從根結(jié)點開始，根結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點。向縱深方向考慮第一個部件從第一個供應商處購買，得到一個新結(jié)點。判斷當前的機器價格(c11)是否超過上限(cc)，重量(w11)是否比當前已知的解(最小重量)大，若是，應回溯至最近的一個活結(jié)點；若否，則該新結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點，根結(jié)點不再是擴展結(jié)點。繼續(xù)向縱深方向考慮第二個部件從第一個供應商處購買，得到一個新結(jié)點。同樣判斷當前的機器價格(c11+c21)是否超過上限(cc)，重量(w11+w21)是否比當前已知的解(最小重量)大。若是，應回溯至最近的一個活結(jié)點；若否，則該新結(jié)點成為活結(jié)點，同時也成為當前的擴展結(jié)點，原來的結(jié)點不再是擴展結(jié)點。以這種方式遞歸地在解空間中搜索，直到找到所要求的解或者解空間中已無活結(jié)點為止。
[C代碼]
下面是該算法的C語言實現(xiàn)。
11變量說明
n：機器的部件數(shù)
m：供應商數(shù)
cc：價格上限
w[][]：二維數(shù)組，w[i][j]表示第j個供應商供應的第i個部件的重量
c[][]：二維數(shù)組，c[i]D.表示第j個供應商供應的第i個部件的價格
bestW：滿足價格上限約束條件的最小機器重量
bestC：最小重量機器的價格
bestX[]：最優(yōu)解，一維數(shù)組，bestX[i]表示第i個部件來自哪個供應商
cw：搜索過程中機器的重量
cp：搜索過程中機器的價格
x[]：搜索過程中產(chǎn)生的解，x[i]表示第i個部件來自哪個供應商
i：當前考慮的部件，從0到n-1
j：循環(huán)變量
12函數(shù)backtrack
int n=3;
int m=3;
int cc=4;
int w[3][3]={{1,2,3},{3,2,1},{2,2,2}};
int c[3][3]={{1,2,3},{3,2,1},{2,2,2}};
int bestW=8;
int bestC=0;
int bestX[3]={0，0，0};
int cw=0;
int cp=0;
int x[3]={0，0，0};
int backtrack (int i){
int j=0;
int found=0;
if(i＞n-1){  /*得到問題解*/
bestW=cw;
bestC=cp;
for(j=0; j＜n;  j++){
（1）  ;
}
return 1;
}
if (cp＜=cc)(/*有解*/
found=1;
}
for(j=0;  （2）  ;  j++){
/*第i個部件從第j個供應商購買*/
（3） ;
cw=cw+w[i] [j];
cp=cp+c[i] [j];
if (cp＜=cc&&  （4）){/*深度搜索，擴展當前結(jié)點*/
if (backtrack(i+1)){    found -1;  )
}
/*回溯*/
cw=cw - w[i] [j];
（5） ;
}
return found;
}