最小重量机器设计问题
一、实验目的
1、了解回溯法和分支限界法的基本思想。
2、运用回溯法和分支限界法解决最小重量机器设计问题。
二、实验要求
最小重量机器设计问题:设某一机器由 n 个部件组成,每一种部件可以从 m 个不同的供应
商处购得。设 w
ij
是从供应商 j 处购得的部件 i 的重量,c
ij
是相应的价格。试设计一个算法,
给出总价格不超过 c 的最小重量机器设计。分别用回溯法和分支限界法实现问题的算法。
三、算法思想和实现
1、回溯法
(1)此问题是一棵排列树,设开始时 bestx=[-1,-1,……,-1]则相应的排列树由 x[0:n-1]的所
有排列构成。
(2)找最小重量机器设计的回溯算法 Backtrack 是类 machine 的公有成员。私有数据成员
整型数组 Savex 保存搜索过的路径,到达叶节点后将数据赋值给数组 bestx。成员 bestw 记
录当前最小重量,cc 表示当前花费,cw 表示当前的重量。
(3)在递归函数 Backtrack 中,在保证总花费不超过 c 的情况下:
当 i=n 时,当前扩展结点是排列树的叶节点。此时搜索到一个解,判断此时的最小重量是
否小于当前最小重量,若小于则更新 bestw,并得到搜索路径 bestx。
当 i<n 时,当前扩展结点位于排列树的第 i-1 层。当 x[0:i]的花费小于给定最小花费时,算
法进入排列树的第 i 层,否则将减去相应的子树。算法用变量 cc 记录当前路径 x[0:i]的费用。
#include<iostream>
using namespace std;
#define N 3
#define M 3
int w[N][M]={{1,2,3},{3,2,1},{2,2,2}};
int c[N][M]={{1,2,3},{3,2,1},{2,2,2}};
class machine