(完整word版)最小重量機(jī)器設(shè)計(jì)問題(word文檔良心出品)

1、最小重量機(jī)器設(shè)計(jì)問題1. 問題描述設(shè)某一機(jī)器由 n 個(gè)部件組成，每一個(gè)部件都可以從m個(gè)不同的供應(yīng)商處購得。 設(shè) wij 是從供應(yīng)商 j 處購得的部件 i的重量， cij是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過c 的最小重量機(jī)器設(shè)計(jì)。算法設(shè)計(jì)：對于給定的機(jī)器部件重量和機(jī)器部件價(jià)格，計(jì)算總價(jià)格不超過 d 的最小重量機(jī)器設(shè)計(jì)。2. 算法流程分析設(shè)開始時(shí)bestx二-1,-1,-1則相應(yīng)的排列樹由x0:n-1的所有排列構(gòu)成。找最小重量機(jī)器設(shè)計(jì)的回溯算法 Backtrack是類machine的公有成員。私有數(shù)據(jù)成員整型數(shù)組 Savex 保存搜索過的路徑，到達(dá)葉節(jié)點(diǎn)后將數(shù)據(jù)賦值給數(shù)組 bestx 。

2、成員 bestw 記錄當(dāng)前最小重量，cc表示當(dāng)前花費(fèi)，cw表示當(dāng)前的重量。在遞歸函數(shù) Backtrack 中，在保證總花費(fèi)不超過 c 的情況下： 當(dāng) i=n 時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)是排列樹的葉節(jié)點(diǎn)。此時(shí)搜索到一個(gè)解， 判斷此時(shí)的最小重量是否小于當(dāng)前最小重量， 若小于則更新 bestw，并得到搜索路徑 bestx 。當(dāng) in 時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)位于排列樹的第 i-1 層。當(dāng) x0:i的費(fèi)用。去相應(yīng)的子樹。算法用變量 cc 記錄當(dāng)前路徑 x0:i3. 算法正確性證明通過幾組實(shí)例證明合法的輸入可以得到正確的輸出實(shí)例見附錄第 2 部分。4. 算法復(fù)雜度分析時(shí)間復(fù)雜度是 O（n 2）5. 參考文獻(xiàn)1 王曉東編著

3、，計(jì)算機(jī)算法設(shè)計(jì)與分析（第 4 版）。北京：電子工業(yè)出版社， 2012.26. 附錄1）可執(zhí)行代碼如下：#includeusing namespace std;#define N 50class MinWmechineint n; / 部件個(gè)數(shù)int m; / 供應(yīng)商個(gè)數(shù)int COST; / 題目中的 Cint cw; / 當(dāng)前的重量int cc; / 當(dāng)前花費(fèi)int bestw; / 當(dāng)前最小重量int bestxN;int savexN;int wNN;int cNN;public:MinWmechine();void machine_plan(int i);void prinout()

4、;MinWmechine:MinWmechine()cw=0; / 當(dāng)前的重量cc=0; / 當(dāng)前花費(fèi)bestw=-1; / 當(dāng)前最小重量bestxN;savexN;coutn;coutm;coutCOST;for(int j=0;jm;j+)for(int i=0;in;i+) cout 請輸入第 j+1 個(gè)供應(yīng)商的第 i+1wij;cout 請輸入第 j+1 個(gè)供應(yīng)商的第 i+1cij;if(wij0 | cij0)cout=n)if(cw bestw | bestw=-1)bestw=cw;Pprss anpta cart inihefor(int j=0;jn; j+) /把當(dāng)前搜過的

5、路徑記下來savexj=bestxj;return;for(int j=0; jm; j+) /依次遞歸嘗試每個(gè)供應(yīng)商if(cc+cijCOST)cc+=cij;cw+=wij;bestxi=j;machine_plan(i+1);bestxi=-1;cc-=cij;cw-=wij;void MinWmechine:prinout() int i,j,ccc=0;for(j=0;jm;j+)for(i=0;in;i+)cout 第 j+1 供應(yīng)商的第 i+1 部件重量：wij價(jià)格： cijn;for(j=0; jn; j+)bestxj=-1;machine_plan(0);coutn 最小重

6、量機(jī)器的重量是 : bestwendl;for(int k=0; kn; k+)自供應(yīng)商k+1 部件來coutsavexk+1n;ccc+=cksavexk;coutn該機(jī)器的總價(jià)錢是：cccendl;coute ndl;int mai n(void)Mi nWmechi ne Y;Y.prin out();retur n 0;(2)輸入輸出實(shí)例窩 I Pfdceos File 3 Micro soft Visual StudioMyProj ectsaxDebiig.ax. ore*13421245量啻至啻至啻曙3 2 2 5 ，-cn.-CEl-ol-Qzl-Qzl-fn.,-CCI,-QZLe 卜卜 件件4-件 f-j-l弓弓弓弓 乂口工口忙口尙凋凋14 14 112 2 112 2S=J 2第第第1勺勺勺勺勺勺勺勺-4- UUJ- .UUJ .UUJ A-i XJJ ip JullR r-yw r2_ 2 士商商商商商商商1苛 2應(yīng)應(yīng)應(yīng)應(yīng)應(yīng)應(yīng)應(yīng)應(yīng)1212 怦町百個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)的的的的 中區(qū)11112222商