最小重量機(jī)器設(shè)計(jì)問題.ppt

《最小重量機(jī)器設(shè)計(jì)問題.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、5-3最小重量機(jī)器設(shè)計(jì)問題問題描述最小重量機(jī)器設(shè)計(jì)問題：設(shè)某一機(jī)器由n個部件組成，每一種部件可以從m個不同的供應(yīng)商處購得。設(shè)wij是從供應(yīng)商j處購得的部件i的重量，cij是相應(yīng)的價格。試設(shè)計(jì)一個算法，給出總價格不超過c的最小重量機(jī)器設(shè)計(jì)。算法設(shè)計(jì)：對于給定的機(jī)器部件重量和機(jī)器部件價格，計(jì)算總價格不超過d的最小重量機(jī)器設(shè)計(jì)。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有3個正整數(shù)n，m和d。接下來的2n行，每行n個數(shù)。前n行是c，后n行是w。結(jié)果輸出：將計(jì)算的最小重量及每個部件的供應(yīng)商輸出到文件out

2、put.txt?；厮莘ㄔ诎瑔栴}的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時，要先判斷該結(jié)點(diǎn)是否包含問題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問題的解，則逐層向其祖先結(jié)點(diǎn)回溯。若用回溯法求問題的所有解時，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要已被搜索遍才結(jié)束。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結(jié)束算法思想本題的實(shí)質(zhì)是在解析空間進(jìn)行搜索，進(jìn)行深度優(yōu)先搜索，但是為了節(jié)省空間與時間資源，使用數(shù)組以及條件判斷來模擬基于深度

3、優(yōu)先的回溯法。對于搜索中的每一步，有如下情況：1.不是最后一個零件還沒有考慮完所有商家，選擇每一個零件的商家不是最后一個商家，只有兩種情況，該商家的零件型號符合要求（即包括該零件，已經(jīng)選擇的零件總價格沒有超過價格上限），則確定該零件選擇該商家，并進(jìn)入下一個零件的選擇，或者該商家的零件型號不符合要求，跳過該商家，該零件開始選擇下一個商家。2.每一個零件的最后一個商家已經(jīng)被考慮過，返回上一個零件的選擇。其中對于最后一個零件，一旦商家的零件型號被選中，比較已經(jīng)記錄的最優(yōu)總重量與該采購清單的總重量，如果比最優(yōu)總重量要

4、小，更改最優(yōu)采購清單及最優(yōu)總重量，不再進(jìn)入下一個零件的選擇。對于第一個零件，當(dāng)其所有商家都已被考慮后，就終止。這里使用i表示正在選擇第i個零件，使用a[i]表示第i個零件選擇的商家，i++和i--表示遞進(jìn)或回溯，由于最后判斷終止條件時需要判斷第一個零件選擇到了最后一個商家時，是不是從下層回溯回來的，如果是，則終止，否則，則是第一個零件選擇了最后一個商家，而且將要進(jìn)入下面的零件的選擇，所以使用bool型變量direction表示是否是回溯(false表示由下一層回溯)。實(shí)驗(yàn)代碼結(jié)果截圖Thankyou