题目描述：
某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为Aij。试设计一个布阵方案，使总的攻击力最大。
数据：
防卫点
角色
1
2
3
4
5
1
60
40
80
50
60
2
90
60
80
70
20
3
30
50
40
50
80
4
90
40
30
70
90
5
60
80
90
60
50
Java实现：
import java.util.Scanner; public class Game { static int point; static int[] x; // 当前位置安排 static int n; // 角色 static int[] bestx; // 当前最大攻击力 static int f; // 当前攻击力 static int bestf; // 当前最优值 static int[][] M; // 初始位置数组 // 交换位置 // public static void swap(int a, int b) { int temp = a; a = b; b = temp; } // 回溯函数 public static void backtrack(int i) { if (i > n) { int t = 0; for (int j = 1; j <= n; j++) t += M[x[j]][j]; if (t > bestf) { bestf = t; for (int j = 1; j <= n; j++) bestx[j] = x[j]; } } else { for (int j = i; j <= n; j++) { int temp = x[i]; x[i] = x[j]; x[j] = temp; backtrack(i + 1); temp = x[i]; x[i] = x[j]; x[j] = temp; } } } public static void main(String[] args) { // 输入n个兵种 Scanner in = new Scanner(System.in); n = in.nextInt(); point = in.nextInt(); M = new int[point + 1][n + 1]; x = new int[n + 1]; bestx = new int[n + 1]; f = 0; // 读入数据矩阵 for (int i = 1; i <= point; i++) { for (int j = 1; j <= n; j++) { M[i][j] = in.nextInt(); // System.out.println(M[i][j] + " "); } } for (int i = 1; i <= n; i++) { x[i] = i; } bestf = 0; //回溯找到最优值 backtrack(1); System.out.println(bestf); for (int i = 1; i <= n; i++) { System.out.println( bestx[i] + " "); } System.out.println(); } }