《《算法設(shè)計(jì)》課程報(bào)告--最小重量機(jī)器設(shè)計(jì)問題(共11頁)》由會員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)》課程報(bào)告--最小重量機(jī)器設(shè)計(jì)問題(共11頁)（11頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、精選優(yōu)質(zhì)文檔-----傾情為你奉上
《算法設(shè)計(jì)》課程報(bào)告
課題名稱： 算法設(shè)計(jì)
課題負(fù)責(zé)人名（學(xué)號）： ---
同組成員名單（角色）： ---
指導(dǎo)教師： ---
評閱成績：
評閱意見：
提交報(bào)告時(shí)間：2014年 6 月 17 日
最小重量機(jī)器設(shè)計(jì)問題
計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)
學(xué)生 -- 指導(dǎo)老師 ---
[題目描述] 設(shè)某一機(jī)器由 n 個部件組成，每一種部件都可以從
2、 m 個
不同的供應(yīng)商處購得。高 wij 是從供應(yīng)商 j 處購得的部件 i 的重量，
cij 是相應(yīng)的價(jià)格。
試設(shè)計(jì)一個算法，給出總價(jià)格不超過 c 的最小重量機(jī)器設(shè)計(jì)。
編程任務(wù)： 對于給定的機(jī)器部件重量和機(jī)器部件價(jià)格，編程計(jì)算總價(jià)
格不超過 d 的最小重量機(jī)器設(shè)計(jì)。
數(shù)據(jù)輸入：由文件 input.txt 給出輸入數(shù)據(jù)。第一行有 3 個正整數(shù) n，
m 和 d。接正業(yè)的 2n 行，每行 n 個數(shù)。前 n 行是 c，后 n 行是 w。
結(jié)果輸出： 將計(jì)算出的最小重量， 以及每個部件的供應(yīng)商輸出到文件
output.txt。
輸入文件示例 輸出文件示例
3、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
[算法分析]
采用回溯算法和分支定界法分別實(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)解。
兩種算法是時(shí)間復(fù)雜度都是O(m^n) ，空間復(fù)雜度均為O(nm
4、)，但由于分支定界法在已經(jīng)排好序的序列中查找，因此查找到的第一個解即為最優(yōu)解，理論上來說，時(shí)間效率會比回溯法高。
[程序?qū)崿F(xiàn)]
回溯法代碼
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF
#define MAXSIZE 100+1
int cur_solution[MAXSIZE];
int solution
5、[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){
if(t>n){
if(cur_minWeight < minWeight){//保存最優(yōu)解和最優(yōu)值
minWeight = cur_minWeight;
for(int r=1;r<=n;++r){
solution[r] = cur_solu
6、tion[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];
}
}
r
7、eturn;
}
int main(){
int n,m,d;
cout<<"Please input the input :"<>strPath;
ofstream fout(strPath);
if(fin.good() && fout.good()){
minWeight = INF
8、;
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<
9、out<
#include
#include
#include
10、
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=c)--r;
t=s[r];s[r]=
11、s[l];s[l]=t;
while(l que;
list::iterator it;
node *pnode;
/* 讀取
12、文件 */
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;i
13、,"%d",p+i*m+j);
fclose(pf);
}
else
{
printf("no input file!!\n");
getchar();
exit(0);
}
/* 準(zhǔn)備數(shù)據(jù) */
int s[n][m]; //用來為每一種零件的質(zhì)量排序，
for(i=0;i
14、/買了n個零件之后，不需要再買了
for(i=0;i=0;--i) //計(jì)算買剩下的零件至少要多少錢
{
minprice[i]=minprice[i+1]+minprice[i];
}
for(i=0;i
15、錄的s中,排序后w[i*m+s[i][j]]，i相同時(shí)，對于變量j是遞增的
qs(w+i*m,s[i],0,m-1);
/* 開始計(jì)算 */
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;
16、 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(levelweight=weight+w[level
17、*m+s[level][i]];
pnode->price=price+p[level*m+s[level][i]];
if(pnode->price+minprice[level+1]<=c) //剪枝，如果當(dāng)前結(jié)點(diǎn)剩下的錢不夠買全所有零件，則剪掉
{
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)先隊(duì)列
if(pnode->
18、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)
19、;
}
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
《算法設(shè)計(jì)》課程報(bào)告--最小重量機(jī)器設(shè)計(jì)問題(共11頁)
