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

代碼如下:


你可能感興趣的試題

2.單項選擇題分治算法設(shè)計技術(shù)()

A.一般由三個步驟組成:問題劃分、遞歸求解、合并解
B.一定是用遞歸技術(shù)來實現(xiàn)
C.將問題劃分為k個規(guī)模相等的子問題
D.劃分代價很小而合并代價很大

最新試題

在有n個無序無重復(fù)元素值的數(shù)組中查找第i小的數(shù)的算法描述如下:任意取一個元素r,用劃分操作確定其在數(shù)組中的位置,假設(shè)元素r為第k小的數(shù)。若i等于k,則返回該元素值;若i小于k,則在劃分的前半部分遞歸進行劃分操作找第i小的數(shù);否則在劃分的后半部分遞歸進行劃分操作找第k-i小的數(shù)。該算法是一種基于()策略的算法。

題型:單項選擇題

代碼如下:

題型:問答題

分治算法設(shè)計技術(shù)()

題型:單項選擇題

設(shè)算法A的時間復(fù)雜度可用遞歸式表示,算法B的時間復(fù)雜度可用遞歸表示,若要使得算法B漸進地快于算法A,則a的最大整數(shù)為()

題型:單項選擇題

某算法的時間復(fù)雜度可用遞歸式表示,若由Θ表示,則正確的是()

題型:單項選擇題

要在8×8的棋盤上擺放8個"皇后",要求"皇后"之間不能發(fā)生沖突,即任何兩個"皇后"不能在同一行、同一列和相同的對角線上,則一般采用()來實現(xiàn)。

題型:單項選擇題

對n個元素值分別為-1、0或1的整型數(shù)組A進行升序排序的算法描述如下:統(tǒng)計A中-1、0和1的個數(shù),設(shè)分別為n1、n2和n3,然后將A中的前n1個元素賦值為-1,第n1+1到n1+n2個元素賦值為0,最后n3個元素賦值為1。該算法的時間復(fù)雜度和空間復(fù)雜度分別為()。

題型:單項選擇題