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

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

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

3、間復(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+1int cur_solut

4、ionMAXSIZE;int solutionMAXSIZE;int wMAXSIZEMAXSIZE; /weightint cMAXSIZEMAXSIZE; /costint minWeight;int cur_minWeight;void Backtrack(int t,int n,int m,int d)if(t>n)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

5、<=m;+i)d -= cti;cur_solutiont = i;cur_minWeight += wti;if(d>=0)Backtrack(t+1,n,m,d);cur_minWeight -= wti;/if(Constraint(t) && Bound(t)Backtrack(t+1,n,m,d);d += cti;return;int main()int n,m,d;cout<<"Please input the input file path:"<<endl;char strPath63;while(scan

6、f("%s",strPath)=1)ifstream fin(strPath);cout<<"Please input the output file path:"<<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

7、<=m;+k) fin>>cjk;for(j=1;j<=n;+j)for(k=1;k<=m;+k) fin>>wjk;Backtrack(1,n,m,d);fout<<minWeight<<endl;for(int r=1;r<=n;+r)fout<<solutionr<<""fout<<endl;fout.close();fin.close();elsecout<<"Open file error!"<<endl;)cou

8、t<<endl<<endl<<"Please input the input file path:"<<endl;)return 0;)分支定界法代碼#include <stdio.h>#include <stdlib.h>#include <list>#include <iostream>using namespace std;#define MAX_NODE 256typedef struct _nodeint weight,price;int level,th;struct

9、 _node *prev;node;void qs(int *a,int *s,int b,int e)快速排序int t,c=asb;int l=b,r=e;while(l<r)while(l<r&&asr>=c)-r;t=sr;sr=sl;sl=t;while(l<r&&asl<c)+l;t=sr;sr=sl;sl=t;if(b<l)qs(a,s,b,l-1);if(l<e)qs(a,s,l+1,e);)int main()(int *w=0,*p=0,n,m,c,i,j;int *minprice;int leve

10、l,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&

11、lt;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();)/*準(zhǔn)備數(shù)據(jù) */int snm;用來為每一種零件的質(zhì)量排序，for(i=0;i<n;+i)for(j=0;j<m;+j)sij=j；minprice=(int*)malloc(n+1)*sizeof(int);/用來記錄買了i 個零

12、件后，買完剩下的零件至少還要多少錢minpricen=0;/買了 n個零件之后，不需要再買了for(i=0;i<n;+i)minpricei=pi*m;for(j=1;j<m;+j) 找出買第i個零件的最低價格 minpricei=minpricei<pi*m+j?minpricei:pi*m+j;)for(i=n-2;i>=0;-i)計(jì)算買剩下的零件至少要多少錢minpricei=minpricei+1+minpricei;)for(i=0;i<n;+i)每種零件按重量排序，排序下標(biāo)記錄的s中，排序后wi*m+sij , i相同時，對于變量j是遞增的qs(w+i

13、*m,si,0,m-1);/*開始計(jì)算 */for(i=0;i<m;+i)初始數(shù)據(jù)把第一種零件的所有情況放入活結(jié)點(diǎn)隊(duì)列pnode=new node;pnode->weight=ws0i;pnode->price=ps0i;if(pnode->price+minprice2<=c) (pnode->th=i;pnode->level=1;pnode->prev =0;que.push_back(pnode); else delete pnode; while(!que.empty()計(jì)算，直到得出結(jié)果或者隊(duì)列為空(level =que.front(

14、)->level;price =que.front()->price;weight=que.front()->weight;if(level<n)for(i=0;i<m;+i)如果隊(duì)首不為葉子結(jié)點(diǎn)，擴(kuò)展隊(duì)首結(jié)點(diǎn)(pnode=new node;pnode->weight=weight+wlevel*m+sleveli;pnode->price=price+plevel*m+sleveli;if(pnode->price+minpricelevel+1<=c) 剪枝，如果當(dāng)前結(jié)點(diǎn)剩下的錢不夠買全所有零件，則剪掉(pnode->th=sle

15、veli;pnode->level=level+1;pnode->prev =que.front();for(it=que.begin();it!=que.end();+it)按重量遞增構(gòu)造優(yōu)先隊(duì)列if(pnode->weight<(*it)->weight)break;que.insert(it,pnode);退出循環(huán)if(level=n-1)break;如果已經(jīng)找到答案,)else delete pnode;)que.pop_front();if(i<m)break;如果已經(jīng)找到答案，退出循環(huán))/*輸出答案 */if(pnode->level!=n

16、)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;i<n;+i)fprintf(pf,"%d ",ansi);fputc('n',pf);fclose(pf);if(minprice)free(minprice);if(w)free(w);if(p)free(p);return 0;運(yùn)行結(jié)果回溯法運(yùn)行結(jié)果如下，分支定界法結(jié)果與下列一致，讀者可以自行運(yùn)行比對' C：Use rsAd rninistrato rD eski c»phorrie算法設(shè)計(jì)作U? wo rkDellease input the input flie path：XUsersXAdministE'atorXDesktDpXl _txt lease input the output file path=: