《算法設(shè)計》課程報告--最小重量機器設(shè)計問題

《算法設(shè)計》課程報告 課題名稱： 算法設(shè)計 課題負責(zé)人名（學(xué)號） ： --- 同組成員名單（角色） ： --- 指導(dǎo)教師： --- 評閱成績： 評閱意見： 提交報告時間： 2014 年 6 月 17 日 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： 最小重量機器設(shè)計問題 計算機科學(xué)與技術(shù) 專業(yè) 學(xué)生 -- 指導(dǎo)老師 --- [ 題目描述 ] 設(shè)某一機器由 n 個部件組成，每一種部件都可以從 m 個 不同的供應(yīng)商處購得。高 wij 是從供應(yīng)商 j 處購得的部件 i 的重量， cij 是相應(yīng)的價格。 試設(shè)計一個算法，給出總價格不超過 c 的最小重量機器設(shè)計。 編程任務(wù)： 對于給定的機器部件重量和機器部件價格，編程計算總價 格不超過 d 的最小重量機器設(shè)計。 數(shù)據(jù)輸入：由文件 input.txt 給出輸入數(shù)據(jù)。第一行有 3 個正整數(shù) n， m 和 d。接正業(yè)的 2n 行，每行 n 個數(shù)。前 n 行是 c，后 n 行是 w 。 結(jié)果輸出： 將計算出的最小重量， 以及每個部件的供應(yīng)商輸出到文件 output.txt 。 輸入文件示例 輸出文件示例 input.txt output.txt 3 3 4 4 1 2 3 1 3 1 3 2 1 2 2 2 1 2 3 3 2 1 2 2 2 -1- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： [ 算法分析 ] 采用回溯算法和分支定界法分別實現(xiàn)，對于回溯法，采用深度優(yōu) 先搜索對子集樹進行剪枝，剪枝條件是當前的總費用不超過總費用； 對于分支定界法，采用按照層次遍歷對子集樹進行剪枝，并將每層的 結(jié)點按照重量由小到大進行排序，將相應(yīng)下標保存在二維數(shù)組 s 中， 以便構(gòu)造最優(yōu)解。 兩種算法是時間復(fù)雜度都是 O(m^n) ，空間復(fù)雜度均為 O(nm) ， 但由于分支定界法在已經(jīng)排好序的序列中查找，因此查找到的第一個 解即為最優(yōu)解，理論上來說，時間效率會比回溯法高。 [ 程序?qū)崿F(xiàn) ] 回溯法代碼 #include <iostream> #include <stdlib.h> #include <fstream> #include <vector> #include <stdio.h> #include <string.h> using namespace std; #define INF 999999999 #define MAXSIZE 100+1 int cur_solution[MAXSIZE]; int solution[MAXSIZE]; int w[MAXSIZE][MAXSIZE]; //weight int c[MAXSIZE][MAXSIZE]; //cost int minWeight; int cur_minWeight; void Backtrack(int t,int n,int m,int d){ -2- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： if(t>n){ if(cur_minWeight < minWeight){// 保存最優(yōu)解和最優(yōu)值 minWeight = cur_minWeight; for(int r=1;r<=n;++r){ solution[r] = cur_solution[r]; } } } else{ for(int i=1;i<=m;++i){ d -= c[t][i]; cur_solution[t] = i; cur_minWeight += w[t][i]; if(d>=0) { Backtrack(t+1,n,m,d); } cur_minWeight -= w[t][i]; //if(Constraint(t) && Bound(t)) Backtrack(t+1,n,m,d); d += c[t][i]; } } return; } int main(){ int n,m,d; cout<<"Please input the input :"<<endl; char strPath[63]; while(scanf("%s",strPath)==1){ ifstream fin(strPath); -3- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： cout<<"Please input the output :"<<endl; cin>>strPath; ofstream fout(strPath); if(fin.good() && fout.good()){ minWeight = INF; cur_minWeight = 0; fin>>n>>m>>d; int j,k; for(j=1;j<=n;++j){ for(k=1;k<=m;++k){ fin>>c[j][k]; } } for(j=1;j<=n;++j){ for(k=1;k<=m;++k){ fin>>w[j][k]; } } Backtrack(1,n,m,d); fout<<minWeight<<endl; for(int r=1;r<=n;++r){ fout<<solution[r]<<" "; } fout<<endl; fout.close(); fin.close(); } else{ cout<<"Open !"<<endl; exit(0); -4- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： } cout<<endl<<endl<<"Please input the input :"<<endl; } return 0; } 分支定界法代碼 #include <stdio.h> #include <stdlib.h> #include <list> #include <iostream> using namespace std; #define MAX_NODE 256 typedef struct _node { int weight,price; int level,th; struct _node *prev; }node; void qs(int *a,int *s,int b,int e)// 快速排序 { int t,c=a[s[b]]; int l=b,r=e; while(l<r) { while(l<r&&a[s[r]]>=c)--r; t=s[r];s[r]=s[l];s[l]=t; while(l<r&&a[s[l]]<c)++l; t=s[r];s[r]=s[l];s[l]=t; } if(b<l)qs(a,s,b,l-1); -5- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： if(l<e)qs(a,s,l+1,e); } int main() { int *w=0,*p=0,n,m,c,i,j; int *minprice; int level,price,weight; list<node*> que; list<node*>::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;i<n;++i) for(j=0;j<m;++j) fscanf(pf,"%d",w+i*m+j); for(i=0;i<n;++i) for(j=0;j<m;++j) fscanf(pf,"%d",p+i*m+j); fclose(pf); } else { printf("no input file!!\n"); getchar(); exit(0); -6- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： } /* 準備數(shù)據(jù) */ int s[n][m]; // 用來為每一種零件的質(zhì)量排序， for(i=0;i<n;++i) for(j=0;j<m;++j) s[i][j]=j; minprice=(int*)malloc((n+1)*sizeof(int));// 用來記錄買了 i 個零件 后，買完剩下的零件至少還要多少錢 minprice[n]=0; // 買了 n 個零件之后，不需要再買了 for(i=0;i<n;++i) { minprice[i]=p[i*m]; for(j=1;j<m;++j) // 找出買第 i 個零件的最低價格 { minprice[i]=minprice[i]<p[i*m+j]?minprice[i]:p[i*m+j]; } } for(i=n-2;i>=0;--i) // 計算買剩下的零件至少要多少錢 { minprice[i]=minprice[i+1]+minprice[i]; } for(i=0;i<n;++i) // 每種零件按重量排序，排序下標記錄的 s 中 , 排序后 w[i*m+s[i][j]] ， i 相同時，對于變量 j 是遞增的 qs(w+i*m,s[i],0,m-1); /* 開始計算 */ for(i=0;i<m;++i) // 初始數(shù)據(jù)把第一種零件的所有情況放入活結(jié) 點隊列 { pnode=new node; pnode->weight=w[s[0][i]]; -7- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： pnode->price=p[s[0][i]]; if(pnode->price+minprice[2]<=c) { pnode->th=i; pnode->level=1; pnode->prev =0; que.push_back(pnode); } else delete pnode; } while(!que.empty()) // 計算，直到得出結(jié)果或者隊列為空 { level =que.front()->level; price =que.front()->price; weight=que.front()->weight; if(level<n)for(i=0;i<m;++i) // 如果隊首不為葉子結(jié)點，擴 展隊首結(jié)點 { pnode=new node; pnode->weight=weight+w[level*m+s[level][i]]; pnode->price=price+p[level*m+s[level][i]]; if(pnode->price+minprice[level+1]<=c) // 剪枝，如果當前結(jié) 點剩下的錢不夠買全所有零件，則剪掉 { pnode->th=s[level][i]; pnode->level=level+1; pnode->prev =que.front(); for(it=que.begin();it!=que.end();++it) // 按 重 量 遞 增構(gòu)造優(yōu)先隊列 if(pnode->weight<(*it)->weight) -8- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： break; que.insert(it,pnode); if(level==n-1)break; // 如果已經(jīng)找到答案，退 出循環(huán) } else delete pnode; } que.pop_front(); if(i<m)break; // 如果已經(jīng)找到答案，退出循環(huán) } /* 輸出答案 */ if(pnode->level!=n) { printf("can not find answer!!"); getchar(); exit(0); } pf=fopen("output.txt","w"); if(pf) { fprintf(pf,"%d\n",pnode->weight); int count=n,ans[n]; while(pnode) { ans[--count]=pnode->th; pnode=pnode->prev; } for(i=0;i<n;++i) fprintf(pf,"%d ",ans[i]); fputc(\n,pf); -9- 課程名稱： 學(xué)生姓名： 學(xué)生學(xué)號： fclose(pf); } if(minprice)free(minprice); if(w)free(w); if(p)free(p); return 0; } [ 運行結(jié)果 ] 回溯法運行結(jié)果如下，分支定界法結(jié)果與下列一致，讀者可以自行運行比對 參考文獻 [1] 王曉東 . 計算機算法設(shè)計與分析 .--3 版 .-- 北京：電子工業(yè)出版社 2007.5 -10-