《算法設計》課程報告課題名稱： 算法設計 課題負責人名（學號）： --- 同組成員名單（角色）： --- 指導教師： --- 評閱成績： 評閱意見： 提交報告時間：2014年 6 月 17 日最小重量機器設計問題計算機科學與技術 專業(yè)學生 -- 指導老師 ---[題目描述] 設某一機器由 n 個部件組成，每一種部件都可以從 m 個不同的供應商處購得高 wij 是從供應商 j 處購得的部件 i 的重量，cij 是相應的價格試設計一個算法，給出總價格不超過 c 的最小重量機器設計編程任務： 對于給定的機器部件重量和機器部件價格，編程計算總價格不超過 d 的最小重量機器設計數(shù)據(jù)輸入：由文件 input.txt 給出輸入數(shù)據(jù)第一行有 3 個正整數(shù) n，m 和 d接正業(yè)的 2n 行，每行 n 個數(shù)前 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[算法分析]采用回溯算法和分支定界法分別實現(xiàn)，對于回溯法，采用深度優(yōu)先搜索對子集樹進行剪枝，剪枝條件是當前的總費用不超過總費用；對于分支定界法，采用按照層次遍歷對子集樹進行剪枝，并將每層的結點按照重量由小到大進行排序，將相應下標保存在二維數(shù)組s中，以便構造最優(yōu)解。
兩種算法是時間復雜度都是O(m^n) ，空間復雜度均為O(nm)，但由于分支定界法在已經(jīng)排好序的序列中查找，因此查找到的第一個解即為最優(yōu)解，理論上來說，時間效率會比回溯法高[程序?qū)崿F(xiàn)]回溯法代碼#include #include #include #include #include #include using namespace std;#define INF 999999999#define MAXSIZE 100+1int cur_solution[MAXSIZE];int solution[MAXSIZE];int w[MAXSIZE][MAXSIZE]; //weightint c[MAXSIZE][MAXSIZE]; //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){ 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 file path:"<>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<#include #include #include using namespace std;#define MAX_NODE 256typedef 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=c)--r; t=s[r];s[r]=s[l];s[l]=t; while(l 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;i=0;--i) //計算買剩下的零件至少要多少錢 { minprice[i]=minprice[i+1]+minprice[i]; } for(i=0;iweight=w[s[0][i]]; 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()) //計算，直到得出結果或者隊列為空 { level =que.front()->level; price =que.front()->price; weight=que.front()->weight; if(levelweight=weight+w[level*m+s[level][i]]; pnode->price=price+p[level*m+s[level][i]]; if(pnode->price+minprice[level+1]<=c) //剪枝，如果當前結點剩下的錢不夠買全所有零件，則剪掉 { pnode->th=s[level][i]; pnode->level=level+1; pnode->prev =que.front(); for(it=que.begin();it!=que.end();++it) //按重量遞增構造優(yōu)先隊列 if(pnode->weight<(*it)->weight) 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,"%d\n",pnode->weight); int count=n,ans[n]; while(pnode) { ans[--count]=pnode->th; pnode=pnode->prev; } for(i=0;i
