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

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

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

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

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

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

信管網(wǎng)考友試題答案分享：

信管網(wǎng)試題答案與解析：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2025/5/21