- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
课程名称: 学生姓名: 学生学号:
《算法设计》课程报告
课题名称: 算法设计
课题负责人名(学号):
同组成员名单(角色):
指导教师:
评阅成绩:
评阅意见:
提交报告时间:2014年 6 月 17 日
最小重量机器设计问题
计算机科学与技术 专业
学生 -- 指导老师
[题目描述] 设某一机器由 n 个部件组成,每一种部件都可以从 m 个
不同的供应商处购得。高 wij 是从供应商 j 处购得的部件 i 的重量,
cij 是相应的价格。
试设计一个算法,给出总价格不超过 c 的最小重量机器设计。
编程任务: 对于给定的机器部件重量和机器部件价格,编程计算总价
格不超过 d 的最小重量机器设计。
数据输入:由文件 input.txt 给出输入数据。第一行有 3 个正整数 n,
m 和 d。接正业的 2n 行,每行 n 个数。前 n 行是 c,后 n 行是 w。
结果输出: 将计算出的最小重量, 以及每个部件的供应商输出到文件
output.txt。
输入文件示例 输出文件示例
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
[算法分析]
采用回溯算法和分支定界法分别实现,对于回溯法,采用深度优先有哪些信誉好的足球投注网站对子集树进行剪枝,剪枝条件是当前的总费用不超过总费用;对于分支定界法,采用按照层次遍历对子集树进行剪枝,并将每层的结点按照重量由小到大进行排序,将相应下标保存在二维数组s中,以便构造最优解。
两种算法是时间复杂度都是O(m^n) ,空间复杂度均为O(nm),但由于分支定界法在已经排好序的序列中查找,因此查找到的第一个解即为最优解,理论上来说,时间效率会比回溯法高。
[程序实现]
回溯法代码
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <stdio.h>
#include <string.h>
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){
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);
cout<<"Please input the output file path:"<<endl;
cin>>strPath;
ofstream fout(strPath);
if(fin.good() && fout.good()){
minWeight = INF;
cur_
文档评论(0)