C++ 深度优先搜索算法求解矩阵最大乘积之和

#include #include using namespace std;

int ans = -1; // 用于保存最大乘积之和的全局变量

// 深度优先搜索函数 void dfs(int i, vector<vector>& p, vector<vector>& q, vector& vis, vector& step) { int n = p.size();

// 如果搜索到达最后一层，则计算乘积之和并更新最大值
if (i == n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += p[i][step[i]] * q[step[i]][i];
    if (sum > ans)
        ans = sum;
    return;
}

// 遍历当前层次的所有可能选择
for (int j = 0; j < n; j++) {
    if (vis[j] == 0) { // 如果该选择未被访问过
        vis[j] = 1; // 标记该选择为已访问
        step[i] = j; // 保存该选择到步长数组中的第 i 个位置
        dfs(i + 1, p, q, vis, step); // 递归调用进行下一层次的搜索
        step[i] = 0; // 回溯时重置步长数组中的第 i 个位置为 0
        vis[j] = 0; // 取消对该选择的访问标记
    }
}

}

int main() { int n; cin >> n; // 读取矩阵的维度

// 创建大小为 n × n 的二维向量 p 和 q 作为输入矩阵
vector<vector<int>> p(n, vector<int>(n, 0));
vector<vector<int>> q(n, vector<int>(n, 0));

// 创建访问标记数组和步长数组，初始值为全 0
vector<int> vis(n, 0);
vector<int> step(n, 0);

// 读取矩阵 p 的元素值
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> p[i][j];
    }
}

// 读取矩阵 q 的元素值
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> q[i][j];
    }
}

// 调用深度优先搜索函数进行搜索
dfs(0, p, q, vis, step);

// 输出最大乘积之和
cout << ans << endl;

return 0;

}