题目描述：

某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有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();

	}
}