




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、算法設計課程報告課題名稱: 算法設計 課題負責人名(學號): - 同組成員名單(角色): -指導教師: -評閱成績: 評閱意見: 提交報告時間:2014年 6 月 17 日最小重量機器設計問題計算機科學與技術 專業(yè)學生 - 指導老師 -題目描述 設某一機器由 n 個部件組成,每一種部件都可以從 m 個不同的供應商處購得。高 wij 是從供應商 j 處購得的部件 i 的重量,cij 是相應的價格。試設計一個算法,給出總價格不超過 c 的最小重量機器設計。編程任務: 對于給定的機器部件重量和機器部件價格,編程計算總價格不超過 d 的最小重量機器設計。數據輸入:由文件 input.txt 給出輸入數
2、據。第一行有 3 個正整數 n,m 和 d。接正業(yè)的 2n 行,每行 n 個數。前 n 行是 c,后 n 行是 w。結果輸出: 將計算出的最小重量, 以及每個部件的供應商輸出到文件output.txt。輸入文件示例 輸出文件示例input.txt output.txt3 3 4 41 2 3 1 3 13 2 12 2 21 2 33 2 12 2 2算法分析采用回溯算法和分支定界法分別實現,對于回溯法,采用深度優(yōu)先搜索對子集樹進行剪枝,剪枝條件是當前的總費用不超過總費用;對于分支定界法,采用按照層次遍歷對子集樹進行剪枝,并將每層的結點按照重量由小到大進行排序,將相應下標保存在二維數組s中,以
3、便構造最優(yōu)解。兩種算法是時間復雜度都是o(mn) ,空間復雜度均為o(nm),但由于分支定界法在已經排好序的序列中查找,因此查找到的第一個解即為最優(yōu)解,理論上來說,時間效率會比回溯法高。程序實現回溯法代碼#include #include #include #include #include #include using namespace std;#define inf 999999999#define maxsize 100+1int cur_solutionmaxsize;int solutionmaxsize;int wmaxsizemaxsize; /weightint cmaxsi
4、zemaxsize; /costint minweight; int cur_minweight;void backtrack(int t,int n,int m,int d)if(tn)if(cur_minweight minweight)/保存最優(yōu)解和最優(yōu)值minweight = cur_minweight;for(int r=1;r=n;+r)solutionr = cur_solutionr;elsefor(int i=1;i=0) backtrack(t+1,n,m,d);cur_minweight -= wti;/if(constraint(t) & bound(t) backtr
5、ack(t+1,n,m,d);d += cti;return;int main()int n,m,d;coutplease input the input file path:endl;char strpath63;while(scanf(%s,strpath)=1)ifstream fin(strpath);coutplease input the output file path:strpath;ofstream fout(strpath);if(fin.good() & fout.good()minweight = inf;cur_minweight = 0;finnmd;int j,k
6、;for(j=1;j=n;+j)for(k=1;kcjk;for(j=1;j=n;+j)for(k=1;kwjk;backtrack(1,n,m,d);foutminweightendl;for(int r=1;r=n;+r)foutsolutionr ;foutendl;fout.close();fin.close();elsecoutopen file error!endl;exit(0);coutendlendlplease input the input file path:endl;return 0;分支定界法代碼#include #include #include #include
7、 using namespace std;#define max_node 256typedef struct _nodeint weight,price;int level,th;struct _node *prev;node;void qs(int *a,int *s,int b,int e)/快速排序 int t,c=asb; int l=b,r=e; while(lr) while(l=c)-r; t=sr;sr=sl;sl=t; while(lr&aslc)+l; t=sr;sr=sl;sl=t; if(bl)qs(a,s,b,l-1); if(le)qs(a,s,l+1,e);in
8、t main()int *w=0,*p=0,n,m,c,i,j;int *minprice;int level,price,weight;list que;list:iterator it;node *pnode;/* 讀取文件 */file *pf;if(pf=fopen(input.txt,r)!=0)fscanf(pf,%d%d%d,&n,&m,&c);w=(int *)malloc(n*m*sizeof(int);/重量p=(int *)malloc(n*m*sizeof(int);/價格for(i=0;in;+i)for(j=0;jm;+j)fscanf(pf,%d,w+i*m+j)
9、;for(i=0;in;+i)for(j=0;jm;+j)fscanf(pf,%d,p+i*m+j);fclose(pf);elseprintf(no input file!n);getchar();exit(0);/* 準備數據 */int snm;/用來為每一種零件的質量排序,for(i=0;in;+i)for(j=0;jm;+j)sij=j;minprice=(int*)malloc(n+1)*sizeof(int);/用來記錄買了i個零件后,買完剩下的零件至少還要多少錢minpricen=0;/買了n個零件之后,不需要再買了for(i=0;in;+i)minpricei=pi*m;fo
10、r(j=1;jm;+j)/找出買第i個零件的最低價格minpricei=minpricei=0;-i)/計算買剩下的零件至少要多少錢minpricei=minpricei+1+minpricei;for(i=0;in;+i)/每種零件按重量排序,排序下標記錄的s中,排序后wi*m+sij,i相同時,對于變量j是遞增的qs(w+i*m,si,0,m-1);/* 開始計算 */for(i=0;iweight=ws0i;pnode-price=ps0i;if(pnode-price+minprice2th=i;pnode-level=1;pnode-prev =0;que.push_back(pno
11、de);else delete pnode;while(!que.empty()/計算,直到得出結果或者隊列為空level =que.front()-level;price =que.front()-price;weight=que.front()-weight;if(leveln)for(i=0;iweight=weight+wlevel*m+sleveli;pnode-price=price+plevel*m+sleveli;if(pnode-price+minpricelevel+1th=sleveli;pnode-level=level+1;pnode-prev =que.front(
12、);for(it=que.begin();it!=que.end();+it)/按重量遞增構造優(yōu)先隊列if(pnode-weightweight)break;que.insert(it,pnode);if(level=n-1)break;/如果已經找到答案,退出循環(huán)else delete pnode;que.pop_front();if(ilevel!=n)printf(can not find answer!);getchar();exit(0);pf=fopen(output.txt,w);if(pf)fprintf(pf,%dn,pnode-weight);int count=n,ansn;while(pnode)ans-count=pnode-th;pnode=pnode-prev;for(i=0
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年汽車自動采樣設備項目立項申請報告模板
- 【南昌】江西南昌縣事業(yè)單位招聘筆試歷年典型考題及考點剖析附帶答案詳解
- 文庫發(fā)布:消防課課件
- 桂花嫁接技術教學課件
- 文庫發(fā)布:健康課件
- 課件教學教案
- 昆曲鑒賞教學課件
- 【課件】三角形的外角+課件2025-2026學年人教版數學八年級上冊
- 四年級作文課件講解教學
- 混凝土結構教學課件
- 寄宿學校思政課教案二篇
- 2025中國石化春季招聘統(tǒng)一初選考試筆試參考題庫附帶答案詳解
- 2025年鉗工(技師)職業(yè)技能鑒定試題庫
- 2025年安徽省中考數學試卷真題(含標準答案)
- 人教A版高中數學《數列的概念》優(yōu)秀1課件
- 海姆立克急救(生命的擁抱)課件
- PE管道安裝單元工程質量評定表
- 部編版小學語文二升三暑假銜接專項訓練—看圖寫話含例文
- 河道生態(tài)護岸設計概況
- 應急預案演練記錄表范例
- 鐵程檢用表(共47頁)
評論
0/150
提交評論