【案例分析題】閱讀下列說明和C代碼，將應(yīng)填入（n）處的字句寫在答題紙的對應(yīng)欄內(nèi)。 說明：設(shè)某一機(jī)器由n個(gè)部件組成，每一個(gè)部件都可以從m個(gè)不同的供應(yīng)商處購得。供應(yīng)商j供應(yīng)的部件i具有重量Wij和價(jià)格Cij。設(shè)計(jì)一個(gè)算法，求解總價(jià)格不超過上限cc的最小重量的機(jī)器組成。采用回溯法來求解該問題。首先定義解空間。解空間由長度為n的向量組成，其中每個(gè)分量取值來自集合{1，2，…，m}，將解空間用樹形結(jié)構(gòu)表示。接著從根節(jié)點(diǎn)開始，以深度優(yōu)先的方式搜索整個(gè)解空間。從根節(jié)點(diǎn)開始，根節(jié)點(diǎn)成為活節(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)。向縱深方向考慮第一個(gè)部件從第一個(gè)供應(yīng)商處購買，得到一個(gè)新節(jié)點(diǎn)。判斷當(dāng)前的機(jī)器價(jià)格（C11）是否超過上限（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è)新節(jié)點(diǎn)。同樣判斷當(dāng)前的機(jī)器價(jià)格（C11+C21）是否超過上限（cc），重量（W11+W21）是否比當(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)。以這種方式遞歸地在解空間中搜索，直到找到所要求的解或者解空間中已無活節(jié)點(diǎn)為止。 C代碼：下面是該算法的C語言實(shí)現(xiàn)。 （1）變量說明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è)部件來自哪個(gè)供應(yīng)商。cw：搜索過程中機(jī)器的重量。cp：搜索過程中機(jī)器的價(jià)格。x［］：搜索過程中產(chǎn)生的解，x［i］表示第i個(gè)部件來自哪個(gè)供應(yīng)商。i：當(dāng)前考慮的部件，從0到n-1。j：循環(huán)變量 （2）函數(shù)backtrack

代碼如下：