《算法設(shè)計(jì)》課程報(bào)告--最小重量機(jī)器設(shè)計(jì)問題

1、算法設(shè)計(jì)課程報(bào)告課題名稱：算法設(shè)計(jì)課題負(fù)責(zé)人名（學(xué)號(hào)） ：-同組成員名單（角色） ：-指導(dǎo)教師：-評(píng)閱成績(jī)：評(píng)閱意見：提交報(bào)告時(shí)間：2014 年 6月 17日課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：最小重量機(jī)器設(shè)計(jì)問題計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生-指導(dǎo)老師- 題目描述設(shè)某一機(jī)器由n 個(gè)部件組成，每一種部件都可以從m 個(gè)不同的供應(yīng)商處購得。高wij是從供應(yīng)商j 處購得的部件i 的重量，cij是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過c 的最小重量機(jī)器設(shè)計(jì)。編程任務(wù)：對(duì)于給定的機(jī)器部件重量和機(jī)器部件價(jià)格，編程計(jì)算總價(jià)格不超過d 的最小重量機(jī)器設(shè)計(jì)。數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有3

2、個(gè)正整數(shù)n，m 和d。接正業(yè)的2n 行，每行n 個(gè)數(shù)。前n 行是c，后n 行是w 。結(jié)果輸出：將計(jì)算出的最小重量，以及每個(gè)部件的供應(yīng)商輸出到文件output.txt 。輸入文件示例輸出文件示例input.txtoutput.txt3 3 441 2 31 3 13 2 12 2 21 2 33 2 12 2 2-1-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)： 算法分析采用回溯算法和分支定界法分別實(shí)現(xiàn)，對(duì)于回溯法，采用深度優(yōu)先搜索對(duì)子集樹進(jìn)行剪枝，剪枝條件是當(dāng)前的總費(fèi)用不超過總費(fèi)用；對(duì)于分支定界法，采用按照層次遍歷對(duì)子集樹進(jìn)行剪枝，并將每層的結(jié)點(diǎn)按照重量由小到大進(jìn)行排序，將相應(yīng)下標(biāo)保存在二維數(shù)組s 中，以便

3、構(gòu)造最優(yōu)解。兩種算法是時(shí)間復(fù)雜度都是O(mn) ，空間復(fù)雜度均為O(nm) ，但由于分支定界法在已經(jīng)排好序的序列中查找，因此查找到的第一個(gè)解即為最優(yōu)解，理論上來說，時(shí)間效率會(huì)比回溯法高。 程序?qū)崿F(xiàn)回溯法代碼#include #include #include #include #include #include using namespace std;#define INF 999999999#define MAXSIZE 100+1int cur_solutionMAXSIZE;int solutionMAXSIZE;int wMAXSIZEMAXSIZE; /weightint cMAXS

4、IZEMAXSIZE; /costint minWeight;int cur_minWeight;void Backtrack(int t,int n,int m,int d)-2-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：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(

5、t) & Bound(t) Backtrack(t+1,n,m,d); d += cti;return;int main()int n,m,d;coutPlease input the input :endl;char strPath63;while(scanf(%s,strPath)=1)ifstream fin(strPath);-3-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：coutPlease input the output :strPath;ofstream fout(strPath);if(fin.good() & fout.good()minWeight = INF;cur_minWeig

6、ht = 0;finnmd;int j,k;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 !endl;exit(0);-4-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：coutendlendlPlease input the input :endl;return 0;分支定界法代碼#include #inclu

7、de #include #include 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);-5-課程名稱：學(xué)生姓

8、名：學(xué)生學(xué)號(hào)：if(le)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 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);/價(jià)格for(i=0;in;+i)for(j=0;

9、jm;+j)fscanf(pf,%d,w+i*m+j);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);-6-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：/*準(zhǔn)備數(shù)據(jù)*/int snm;/ 用來為每一種零件的質(zhì)量排序，for(i=0;in;+i)for(j=0;jm;+j)sij=j;minprice=(int*)malloc(n+1)*sizeof(int);/用來記錄買了i個(gè)零件后，買完剩下的零件至少還要多少錢minpricen=0;/ 買

10、了 n 個(gè)零件之后，不需要再買了for(i=0;in;+i)minpricei=pi*m;for(j=1;jm;+j)/ 找出買第i 個(gè)零件的最低價(jià)格minpricei=minpricei=0;-i)/ 計(jì)算買剩下的零件至少要多少錢minpricei=minpricei+1+minpricei;for(i=0;in;+i)/ 每種零件按重量排序，排序下標(biāo)記錄的s 中 ,排序后wi*m+sij， i 相同時(shí)，對(duì)于變量j 是遞增的qs(w+i*m,si,0,m-1);/*開始計(jì)算*/for(i=0;iweight=ws0i;-7-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：pnode-price=ps0i;if

11、(pnode-price+minprice2th=i;pnode-level=1;pnode-prev =0;que.push_back(pnode);else delete pnode;while(!que.empty()/ 計(jì)算，直到得出結(jié)果或者隊(duì)列為空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-p

12、rice+minpricelevel+1th=sleveli;pnode-level=level+1;pnode-prev =que.front();for(it=que.begin();it!=que.end();+it)/按 重 量 遞增構(gòu)造優(yōu)先隊(duì)列if(pnode-weightweight)-8-課程名稱：學(xué)生姓名：學(xué)生學(xué)號(hào)：break;que.insert(it,pnode);if(level=n-1)break;/ 如果已經(jīng)找到答案，退出循環(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;in;+i)fprintf(pf,%