排兵布阵算法

 题目：

某游戏中，不同的兵种处于不同的地形上时，其攻击能力也一样，现有n个不同兵种的角色(1;2;; n)，需安排在某战区n个点上，角色i在j点上的攻击力为Aij，试设计一个布阵方案，使总的攻击力最大。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100+10;

int n,ans=0;
int map[maxn][maxn];
bool vis[maxn];
int pos[maxn],ans_pos[maxn];

void dfs(int cnt,int u)
{
if (cnt == n)
{
if (u > ans)
{
ans=u;
memcpy(ans_pos,pos,sizeof(pos));
}
return;
}
for (int i = 0; i<n; i++)
{
if(!vis[i])
{
vis[i]=1;
pos[cnt]=i+1;
dfs(cnt+1,u+map[cnt][i]);
vis[i]=0;
}
}

}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
}

}

memset(vis,0,sizeof(vis));
dfs(0,0);
printf("Max ATC:%d\n",ans);
printf(" Posion: ");
for(int i=0;i<n;i++)
{
printf("%d",ans_pos[i]);
}

printf("\n");
}
return 0;
}

结果：

排兵布阵算法

原文：https://www.cnblogs.com/T815/p/14162222.html