算法提高 金陵十三钗
金陵十三钗 本题难度：难 本题占分比例：5% 问题描述 在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本人的死亡宴会。为了不让日本人发现，自然需要一番乔装打扮。但由于天生材质的原因，每个人和每个人之间的相似度是不同的。由于我们这是编程题，因此情况就变成了金陵n钗。给出n个女人和n个学生的相似度矩阵，求她们之间的匹配所能获得的最大相似度。 所谓相似度矩阵是一个n*n的二维数组like[i][j]。其中i,j分别为女人的编号和学生的编号，皆从0到n-1编号。like[i][j]是一个0到100的整数值，表示第i个女人和第j个学生的相似度，值越大相似度越大，比如0表示完全不相似，100表示百分之百一样。每个女人都需要找一个自己代替的女学生。 最终要使两边一一配对，形成一个匹配。请编程找到一种匹配方案，使各对女人和女学生之间的相似度之和最大。 输入格式 第一行一个正整数n表示有n个秦淮河女人和n个女学生 接下来n行给出相似度，每行n个0到100的整数，依次对应二维矩阵的n行n列。 输出格式 仅一行，一个整数，表示可获得的最大相似度。 样例输入 4 97 91 68 14 8 33 27 92 36 32 98 53 73 7 17 82 样例输出 354 数据规模和约定 对于70%的数据，n<=10 对于100%的数据，n<=13 样例说明 最大相似度为91+92+93+73=354
代码：
import java.util.Scanner;
/*
* 8皇后的变种
*/
public class Main {
static int N;
static int[][] num;
static int[] b;
static int sum = 0;
public static void dfs(int t){
if ( t == N){
int sum1 = 0;
for ( int i = 0 ; i < N ; i++){
sum1 += num[i][b[i]];
}
sum = Math.max(sum, sum1);
return;
}else{
//第cur个人替代第i个人
for ( int i = 0 ; i < N ; i++){
boolean flag = true;
int j;
for ( j = 0 ; j < t ; j++){
//第i个人已经被替代了
if( b[j] == i){
flag = false;
break;
}
}
if ( flag == true){
b[j] = i;
dfs(t+1);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
N = in.nextInt();
num = new int[N][N];
b = new int[N];
for ( int i = 0 ; i < N ; i++){
for (int j = 0 ; j < N ; j++){
num[i][j] = in.nextInt();
}
}
dfs(0);
System.out.println(sum);
in.close();
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读