问题描述
某游戏中，不同的兵种处于不同的地形上时，其攻击能力也一样，现有n个不同兵种的角色\((1, 2, \cdots, n)\)，需安排在某战区\(n\)个点上，角色\(i\)在\(j\)点上的攻击力为\(A_{ij}\)，试设计一个布阵方案，使总的攻击力最大。注：个人决定A矩阵的初始化工作。
目标函数
\[\max \{ \sum_{i=1}^n power_i\} \]解向量
用元组\((x_1,x_2,...x_n)\)表示解，\(x_i\)表示角色i的位置。
显式约束
\[S_i=\{1,2,...,n\},1\leq i \leq n \]状态空间树
类型
状态空间树是一颗排列树。
候选解规模
叶子结点数有\(n!\)个。
隐式约束
对任意\(1 \leq i,j \leq n\),当\(i \neq j\)时，\(x_i \neq x_j\)
算法设计
算法的伪代码描述
function backTrack(t, n)
if t > n then
power ← 0
for i = 1 → n do
power ← power + power1
if power < powermax then
powermax ← power
x1 ← x
else
for i = 1 → n do
x[t] ← i
if Position(t) then
backTrack(t + 1)
end function
function Position(k)
for i = 1 → k − 1 do
if x[i] == x[k] then
return false
return true
end function
时间复杂度估计
\[W(n) = p(n)f(n) \]\(p(n)\)为求解一个叶子节点的时间，\(f(n)\)为叶子节点的个数
编码实现
#include<iostream>
#include<vector>
using namespace std;
vector<int> x,x1;
vector<vector<int> > p;
int powermax = -1;
int n;
//判断角色k的位置是否可行
bool position(int k){
for(int i = 1;i < k;i ++){
if(x[k] == x[i]){
return false;
}
}
return true;
}
//回溯法求最优解
void backTrack(int t){
if(t > n){//求总攻击力并更新最大值
int power = 0;
for(int i = 1;i <= n;i ++){
power = power + p[i][x[i]];
}
if(power > powermax){
powermax = power;
x1 = x;//记录当前最优解的排列
}
}else{//遍历可行排列
for(int i = 1;i <= n;i ++){
x[t] = i;
if(position(t)){
backTrack(t+1);
}
}
}
}
int main(){
cin >> n;
for(int i = 0;i <= n;i ++){
x.push_back(0);
x1.push_back(0);
}
for(int i = 0;i <= n;i ++){
p.push_back(x);
}
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
int p1;
cin >> p1;
p[i][j] = p1;
}
}
backTrack(1);
cout << "最优解为：" << endl;
for(int i = 1;i <= n;i ++){
cout << x1[i] << " ";
}
cout << "最大攻击力为：" << powermax << endl;
return 0;
}
程序调试与结果展示
结束语
别让怯懦否定了自己，别让懒惰耽误了青春
作者：花城