0345 矩阵和
* * * *
拉格朗日计划
* * * *
矩阵和

给定一个矩阵,从中选择部分元素,使得每个元素都是其所在的行和列中唯一被选中的元素,并取这些被选中元素的和。

称所有可能的选择所产生的和的最大值为该矩阵的矩阵和。例如,以下矩阵的矩阵和为3315 ( = 863 + 383 + 343 + 959 + 767): $$\begin{matrix} 7 & 53 & 183 & 439 & \red{863} \\ 497 & \red{383} & 563 & 79 & 973 \\ 287 & 63 & \red{343} & 169 & 583 \\ 627 & 343 & 773 & \red{959} & 943 \\ \red{767} & 473 & 103 & 699 & 303 \end{matrix}$$ 求如下矩阵的矩阵和: $$\begin{matrix} 7 & 53 & 183 & 439 & 863 & 497 & 383 & 563 & 79 & 973 & 287 & 63 & 343 & 169 & 583 \\ 627 & 343 & 773 & 959 & 943 & 767 & 473 & 103 & 699 & 303 & 957 & 703 & 583 & 639 & 913 \\ 447 & 283 & 463 & 29 & 23 & 487 & 463 & 993 & 119 & 883 & 327 & 493 & 423 & 159 & 743 \\ 217 & 623 & 3 & 399 & 853 & 407 & 103 & 983 & 89 & 463 & 290 & 516 & 212 & 462 & 350 \\ 960 & 376 & 682 & 962 & 300 & 780 & 486 & 502 & 912 & 800 & 250 & 346 & 172 & 812 & 350 \\ 870 & 456 & 192 & 162 & 593 & 473 & 915 & 45 & 989 & 873 & 823 & 965 & 425 & 329 & 803 \\ 973 & 965 & 905 & 919 & 133 & 673 & 665 & 235 & 509 & 613 & 673 & 815 & 165 & 992 & 326 \\ 322 & 148 & 972 & 962 & 286 & 255 & 941 & 541 & 265 & 323 & 925 & 281 & 601 & 95 & 973 \\ 445 & 721 & 11 & 525 & 473 & 65 & 511 & 164 & 138 & 672 & 18 & 428 & 154 & 448 & 848 \\ 414 & 456 & 310 & 312 & 798 & 104 & 566 & 520 & 302 & 248 & 694 & 976 & 430 & 392 & 198 \\ 184 & 829 & 373 & 181 & 631 & 101 & 969 & 613 & 840 & 740 & 778 & 458 & 284 & 760 & 390 \\ 821 & 461 & 843 & 513 & 17 & 901 & 711 & 993 & 293 & 157 & 274 & 94 & 192 & 156 & 574 \\ 34 & 124 & 4 & 878 & 450 & 476 & 712 & 914 & 838 & 669 & 875 & 299 & 823 & 329 & 699 \\ 815 & 559 & 813 & 459 & 522 & 788 & 168 & 586 & 966 & 232 & 308 & 833 & 251 & 631 & 107 \\ 813 & 883 & 451 & 509 & 615 & 77 & 281 & 613 & 459 & 205 & 380 & 274 & 302 & 35 & 805 \\ \end{matrix}$$
本题难度:



解答

记这个$15\times 15$的矩阵为$A$,本题就是求$\mathrm{tr}(AP)$的最大值,其中$\mathrm{tr}$是矩阵的迹,P取遍所有的排列矩阵。

亦即所选取的元素可以写作 $A_{1,c_1},A_{2,c_2},\ldots,A_{15,c_{15}}$,其中$c_1,\ldots,c_{15}$是1到15的一个全排列,需要求出取遍所有的全排列时这些元素和的最大值。

由于下标的上述特性可以对之使用状态压缩,用15位二进制数s来表示目前已经选过的行和列。

行标总是从上到下依次选取,因此若s中二进制为1的数量是m,就表示前m行已经选过了,这些1的位置就表示所选择的列标。

用$f(s)$表示状态s所对应的所有可能选择中元素和的最大值,接下来用动态规划的方式递推更新$f(s)$即可得结果$13938$。

n=15

A=[[7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583],
[627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913],
[447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743],
[217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350],
[960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350],
[870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803],
[973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326],
[322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973],
[445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848],
[414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198],
[184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390],
[821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574],
[34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699],
[815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107],
[813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805]]

f=[0]*(1 << n)

for s in range(1,len(f)):
    c=format(s,"b").count('1')-1
    for i in range(n):
        if s>>i & 1:
            f[s]=max(f[s],f[s^(1 << i)]+A[c][i])

print f[-1]