實驗報告 最小重量機器設計問題.doc

實 驗 報 告課程名稱： 算法設計與分析 實驗項目： 最小重量機器設計問題 實驗類型：綜合性 設計性 驗證性專業(yè)班別： 姓 名： 學 號： 實驗課室： 第 計算機實驗室 指導教師： 實驗日期： 2013-12-12 一、實驗項目訓練方案小組合作：是 否R小組成員：實驗目的：1. 通過回溯法的示例程序理解回溯法的基本思想；2. 運用回溯法解決實際問題進一步加深對回溯法的理解和運用。實驗場地及儀器、設備和材料操作系統(tǒng)： winXP 、 Win7、ubuntu開發(fā)環(huán)境：VC+ 6.0、Visual Studio 2010實驗訓練內容（包括實驗原理和操作步驟）：一、實驗內容：1. 練習使用回溯法求解“最小重量機器設計”問題。二、實驗題題目描述設某一機器由n個部件組成，每一種部件都可以從m個不同的供應商處購得。設 wij 是從供應商j 處購得的部件i的重量， cij 是相應的價格。設計一個優(yōu)先隊列式分支限界法，給出總價格不超過d的最小重量機器設計。對于給定的機器部件重量和機器部件價格，設計一個優(yōu)先隊列式分支限界法，計算總價格不超過d的最小重量機器設計。輸入輸入數(shù)據(jù)的第1 行有3 個正整數(shù)n ，m和d（n，m20，d100）。接下來的2n 行，每行n個數(shù)。前n行是c，后n行是w。輸出將計算出的最小重量，以及每個部件的供應商分成兩行輸出。無解請輸出“No Solution!”。示例輸入3 3 41 2 33 2 12 2 21 2 33 2 12 2 2示例輸出41 3 1三、實驗步驟1理解回溯算法思想和算法示例； 2上機輸入和調試算法示例程序；3理解實驗題的問題要求；4上機輸入和調試自己所編的實驗題程序； 5驗證并分析實驗題的實驗結果；6整理出實驗報告。代碼如下：#include using namespace std; const int len=30;const int maxWeight=4000;int n,m,cost;int wlenlen;/重量int clenlen;/價錢int visitlen;int pathlen;int minWeight = maxWeight;void findMinWeight(int current,int weight,int i) /當前策略的價錢和最小重量 if(i = n) minWeight=weight; for(int j=0; jn; j+) pathj=visitj; return;for(int j=0; jm; j+) if(current+cij=cost & weight+wijnmcost) minWeight = maxWeight; int i,j; for(i=0; i2*n; i+) for(j=0; jm; j+) if(icij; else cinwi-nj; findMinWeight(0,0,0); if(minWeight = maxWeight) cout-1endl; else coutminWeightendl; for(i=0; in; i+) if(i=0) coutpathi; else cout pathi; coutendl; return 0;結果：二、實驗總結與評價實驗總結（包括實