算法第五章《回溯法》上机实践报告

一．实践题目名称

最小重量机器设计问题

 

二．问题描述

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij​是从供应商j 处购得的部件i的重量，cij​是相应的价格。 试设计一个算法，给出总价格不超过d的最小重量机器设计。

输入格式:

第一行有3 个正整数n ，m和d， 0<n<30, 0<m<30, 接下来的2n 行，每行n个数。前n行是c，后n行是w。

输出格式:

输出计算出的最小重量，以及每个部件的供应商

输入样例:

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.请用回溯法的方法分析“最小重量机器设计问题”

路径：以深度优先的方法搜索解空间，并用剪枝函数避免无效的搜索。

剪枝函数：①用约束条件（当前价格+该零件价格<总价格d）剪去不满足约束的子树。

　　　　　②用上界条件（当前重量+该零件重量<最小重量纪录）剪去得不到最优解的子树。

 

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

本题的解空间为总价格不超过d的所有可能的部件重量值，{(1,3,1),(1,3,2),(1,3,3)}

 

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

从根节点出发后，每一层分别表示一个部件的不同供应商，往下延伸共n层。

 

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

每个结点的状态值是从第一个结点到该结点的累计价值和累计重量。

 

#include<iostream>
using namespace std;

int n;  //n个部件
int m;  //m个供应商
int d;  //总价格不超过d
int minw = 1000;  //记录最小重量
int cw = 0;  //记录当前重量
int cp = 0;  //记录当前价格
int w[31][31] = { 0 };  //从j供应商处买到的i部件的重量
int c[31][31] = { 0 };  //从j供应商处买到的i部件的价格
int s[31] = { 0 };  //记录第i个部件的供应商
int mins[31] = { 0 };  //记录最小重量的供应商

void backtrack(int i)
{
    if (i > n)
    {
        if (cw < minw)
        {
            minw = cw;
            for (int i = 1; i <= n; i++)
                mins[i] = s[i];
        }
        return;
    }
    else
    {
        for (int j = 1; j <= m; j++)
        {
            if (cw + w[i][j] < minw && cp + c[i][j] <= d && !s[i])
            {
                cp += c[i][j];
                cw += w[i][j];
                s[i] = j;  //记录当前零件的供应商
                backtrack(i + 1);
                cp -= c[i][j];
                cw -= w[i][j];
                s[i] = 0;
            }
        }
    }
}

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 << minw << endl;
    for (int i = 1; i <= n; i++)
        cout << mins[i] << " ";
    return 0;
}

 

四．对回溯法的理解

回溯法按深度优先策略遍历解空间树，但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。其时间复杂度普遍较高，需利用合适的剪枝函数进行优化。