第五章-最小重量机器设计问题-实验报告

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

1. 请用回溯法的方法分析“最小重量机器设计问题”

1.1 说明“最小重量机器设计问题"的解空间

n个部件，m个不同的供应商，该问题的解空间由长度为n的 0 - 1向量组成。

1.2 说明 “最小重量机器设计问题"的解空间树

第t层到第t+1层代表第t个部件的供应商的选择，每个非叶子节点都有m个分支。

1.3 在遍历解空间树的过程中，每个结点的状态值是什么

cw: 当前的重量     cc: 当前的价格

代码：

#include
#include 
using namespace std;
int n,m,cost; //限定价格 部件数 供应商数
int w[100][100];//w[i][j]为第i个零件在第j个供应商的重量
int c[100][100];//c[i][j]为第i个零件在第j个供应商的价格
int bestx[100];//bestx[i]用来存放第i个零件的最后选择供应商
int x[100];//x[i]临时存放第i个零件的供应商
int cw=0,cc=0,bestw=100000;

void Backtrack(int t)  // t对应 部件t 
{
    if(t>n)//搜索到叶子结点，一个搜索结束，所有零件已经找完
    {
        if(cw<bestw){
            bestw=cw; //当前最小重量
        for(int j=1;j<=n;j++)
            bestx[j]=x[j];
        }
//        return; // 有else就不需要 return，两个选一个 
    }
    else{
        for(int i=1;i<=m;i++)  // 遍历所有供应商 
        {
            cc+=c[t][i];  
            cw+=w[t][i];
            x[t]=i;
            if(cc<=cost && cw<=bestw) // 剪枝操作                     
               Backtrack(t+1);
            cc-=c[t][i];
            cw-=w[t][i];      
        }
    }   
}
 
int main()
{
    cin>>n>>m>>cost;
    for(int i=1; i<=n; i++) //各部件在不同供应商的重量 cij:物品i在供应商j的价格 
        for(int j=1; j<=m; j++)
            cin>>c[i][j];
    for(int i=1; i<=n; i++) //各部件在不同供应商的价格 wij:物品i在供应商j的重量 
        for(int j=1; j<=m; j++)
            cin>>w[i][j];        
    Backtrack(1);
    cout<// 最低的重量 
    for(int i=1;i<=n;i++) // 输出各个部件的供应商 
        cout<" ";
    return 0;
}

2. 你对回溯算法的理解

首先回溯算法是有一个套路模板的，通过一定的训练之后，根据模板我们可以快速的对应到相应的板块，解决回溯问题。

初始化根节点，将根节点入队;
 while (队列 ≠Φ) 
 {
 从队列中取出一节点；（优先级别大（小）者原则）
 若p是目标，则获得最优解；否则产生p的后继，并将后继结点插入队列中（可以按照一定规则淘汰一些结点）
 }

在我看来，回溯法通过深度遍历得到所有最优解，其中为了减少不必要的遍历，会使用剪枝函数，减去不满足要求的路径。