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

《算法设计》课程报告
课题负责人名（学
课题名称： 算法设计
号）: ——
同组成员名单（角色）：
指导教师： ---
评阅成绩：
评阅意见：
提交报告时间：2014年6月17日
最小重量机器设计问题
计算机科学与技术专业 学生-- 指导老师---
［题目描述］ 设某一机器由 n个部件组成，每一种部件都可以从 m个
不同的供应商处购得。高 wij 是从供应商j处购得的部件i的重量，
cij是相应的价格。
试设计一个算法，给出总价格不超过 c的最小重量机器设计。
编程任务： 对于给定的机器部件重量和机器部件价格，编程计算总价
格不超过d的最小重量机器设计。
数据输入：由文件 给出输入数据。第一行有 3个正整数n，
m和d。接正业的 2n行，每行n个数。前n行是c ,后n行是w。
结果输出： 将计算出的最小重量,
以及每个部件的供应商输出到文件

输出文件示例
输入文件示例
in
3 3 4 4
1 2 3 1 3 1
[ 算法分析 ] 采用回溯算法和分支定界法分别实现，对于回溯法，采用深度优先搜索对子集 树进行剪枝，剪枝条件是当前的总费用不超过总费用；对于分支定界法，采用按照 层次遍历对子集树进行剪枝，并将每层的结点按照重量由小到大进行排序，将相应 下标保存在二维数组 s 中，以便构造最优解。
两种算法是时间复杂度都是 。伸八n),空间复杂度均为 0(nm),但由于分支定界
法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说， 时间效率会比回溯法高。
[ 程序实现 ] 回溯法代码 #include <iostream> #include <> #include <fstream> #include <vector> #include <> #include <> using namespace std;
#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){
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];