第五章上机报告
第五章上机报告
计科2001班 洪雯希 20201003069
1、 问题描述
7-2 最小重量机器设计问题 (25 分)
设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij?是从供应商j 处购得的部件i的重量,cij?是相应的价格。 试设计一个算法,给出总价格不超过d的最小重量机器设计。
输入格式:
第一行有3 个正整数n ,m和d, 0 输出格式: 输出计算出的最小重量,以及每个部件的供应商 输入样例: 3 3 4 1 2 3 3 2 1 2 2 2 1 2 3 3 2 1 2 2 2 结尾无空行 输出样例: 在这里给出相应的输出。例如: 4 1 3 1 2、 算法描述 先初始化当前价格cp=0,当前重量cw=0,将选择机器的总重量bestw初始化为每个部件从1号供应商购买的重量,在循环的过程中,判断选择的从j供应商买的机器后价格是否大于总价格,如果小于则选择,如果大于则不选。当所有机器选择结束后,判断得到的总重量是否比之前的bestw小,如果小就赋给bestw,然后从这一步开始,回溯到上一机器,选择下一合适供应商,继续搜索可行解,直到将整个排列树搜索完毕。这样,最终得到的bestw即为最优解。 以深度优先搜索的方法遍历来找到解空间,用剪枝的方法来减少不必要的步骤。 (1) 说明“最小重量机器设计问题”的解空间 一共有n个部件,m个供应商,理论上就有m的n次方个解。 (2) 说明“最小重量机器设计问题”的解空间树 (3)在遍历解空间树的过程中,每个结点的状态是什么 每个结点有两个状态值:当前的总价格、当前的总重量 3、 问题求解 #include using namespace std; int n,m,d;//n个组件 m个供应商 总价格不超过d int c[999][999],w[999][999];//c[i][j],w[i][j] 各表示从供应商j处购得部件i的价格/重量 int cw=0,cp=0;//记录当前最小的重量和价值 int bestw=999,bestp=999;//最小重量 int x[999],bestx[999];//保存当前重量下每个部件供应商的号码 void backtrack(int i) { if(i>n) { if(cp<=d&&cw bestw=cw; bestp=cp; for(int j=1; j<=n; j++) bestx[j]=x[j]; } } else { for(int j=1; j<=m; j++) { x[i]=j;//记录下当前部件是哪一个供应商 cw=cw+w[i][j]; cp=cp+c[i][j]; if(cp<=d&&cw //如果当前供应商的部件可以满足条件 直接进入下一个部件的判断 backtrack(i+1); } //回溯过程 cw=cw-w[i][j]; cp=cp-c[i][j]; } } } int main() { cin>>n>>m>>d; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>c[i][j]; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>w[i][j]; backtrack(1); cout< for(int i=1; i<=n; i++) cout< return 0; } 4、 对回溯算法的理解 在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。