《算法设计》课程报告--最小重量机器设计问题.doc

《算法设计》课程报告课题名称: 算法设计课题负责人名(学号): --- 同组成员名单(角色): --- 指导教师: --- 评阅成绩: 评阅意见: 提交报告时间: 2014 年6月 17日课程名称: 学生姓名: 学生学号: - 1- 最小重量机器设计问题计算机科学与技术专业学生-- 指导老师--- [ 题目描述] 设某一机器由 n 个部件组成,每一种部件都可以从 m个不同的供应商处购得。高 wij 是从供应商 j 处购得的部件 i 的重量, cij 是相应的价格。试设计一个算法,给出总价格不超过 c 的最小重量机器设计。编程任务: 对于给定的机器部件重量和机器部件价格,编程计算总价格不超过 d 的最小重量机器设计。数据输入:由文件 给出输入数据。第一行有 3 个正整数 n, m和d 。接正业的 2n 行,每行 n 个数。前 n 行是 c ,后 n 行是 w。结果输出: 将计算出的最小重量, 以及每个部件的供应商输出到文件 。输入文件示例输出文件示例 3344 123131 321222123321222 课程名称: 学生姓名: 学生学号: - 2- [ 算法分析]采用回溯算法和分支定界法分别实现, 对于回溯法, 采用深度优先搜索对子集树进行剪枝,剪枝条件是当前的总费用不超过总费用; 对于分支定界法, 采用按照层次遍历对子集树进行剪枝, 并将每层的结点按照重量由小到大进行排序,将相应下标保存在二维数组 s 中, 以便构造最优解。两种算法是时间复杂度都是 O(m^n) ,空间复杂度均为 O(nm) , 但由于分支定界法在已经排好序的序列中查找, 因此查找到的第一个解即为最优解,理论上来说,时间效率会比回溯法高。[ 程序实现] 回溯法代码#include <iostream> #include <> #include <fstream> #include <vector> #include <> #include <> 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){ 课程名称: 学生姓名: 学生学号: - 3- if(t>n){ if(cur_minWeight < minWeight){// 保存最优解和最优值 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:"<<endl; char strPath[63]; while(scanf("%s",strPath)==1){ ifstream fin(strPath); 课程名称: 学生姓名: 学生学号: - 4- cout<<"Please input the output file path:"<<endl; cin>>strPath; ofstream fout(strPath); if(() && ()){ 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