Project Euler 345

发表于 更新于 分类于 阅读次数： 本文字数： 2.3k 阅读时长 ≈ 2 分钟

Project Euler 345

题目

Matrix Sum

We define the Matrix Sum of a matrix as the maximum possible sum of matrix elements such that none of the selected elements share the same row or column.

For example, the Matrix Sum of the matrix below equals \(3315 ( = 863 + 383 + 343 + 959 + 767)\):

\[\begin{matrix}   7 &  53 & 183 & 439 & \color{lightgreen} {863} \\ 497 & \color{lightgreen} {383} & 563 &  79 & 973 \\ 287 &  63 & \color{lightgreen} {343} & 169 & 583 \\ 627 & 343 & 773 & \color{lightgreen} {959} & 943 \\ \color{lightgreen} {767} & 473 & 103 & 699 & 303 \end{matrix}\]

Find the Matrix Sum of:

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

解决方案

不难想到使用状态压缩动态规划来完成这题。

令\(N=15\)。并将这些数存在一个开始下标为\(0\)的\(N\times N\)大小的数组中。我们使用一个\(N\)位二进制数\(st\)来表示当前的列的使用情况。如果第\(i\)列被使用了，那么\(st\)的第\(i\)位为\(1\)，否则为\(0\)。并且令\(c(st)\)为\(N\)位二进制数\(st\)中\(1\)的位数。

那么令状态\(f(st)(0\le st<2^N)\)为在前\(c(st)\)行中，已经使用了\(st\)表示的一部分列，目前的最大和。那么可以写出如下状态转移方程：

\[ f(st)= \left \{\begin{aligned} &0 & & \text{if}\quad st=0 \\ &\max_{i=0,st\&2^i>0}^{N-1} \{f(st\oplus2^i)+a[c(st)-1][i]\}& & \text{else} \end{aligned}\right. \]

对于每一个状态\(st\)，通过\(c(st)\)我们就已经确定了当前已经使用的行数，并从新的一行开始选择。最终，从前已经使用的\(f(st\oplus 2^i)\)和现在要选择的\(a[c(st)-1][i]\)数相合并，就转移到了当前状态。

最终答案为\(f[2^N-1]\)，注意\(c(2^N-1)=N\)，这说明\(N\)行都已经被选完了。

另外一种方法则是通过改造求将这个问题转换成最小费用最大流问题，从而可以在多项式时间内解决。

由于同一行下，每一列的元素都是互斥的，这让我们考虑使用网络流的思想解决。因此我们将每一行和每一列都用一个节点表示，假设行节点为\(a_i\)，列节点为\(b_j\)，那么为每个行节点\(a_i\)向列节点\(b_j\) 连一条费用为\(-a[i][j]\)（注意这里是负数，因为问题模型是最小费用），容量为\(1\)的边。添加一个源点\(s\)，指向所有行节点，容量为\(1\)，费用为\(0\)；再添加一个汇点\(t\)，将所有列节点指向\(t\)，同样容量为\(1\)，费用为\(0\)。

最终执行完算法后，花费的费用最小，并且每一行，每一列都被用到。取反符号后即为答案。

此处的代码将使用networkx库中的max_flow_min_cost方法完成。

通过查看费用流的\(N^2\)条边的使用情况，还可以得知哪\(N\)个数被选上了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int N=15;
int a[N][N]={
  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
};
int f[1<<N];
int main(){
    for(int s=1;s<(1<<N);s++){
        int c=__builtin_popcount(s)-1;
        for(int i=0;i<N;i++){
            if(s>>i&1)
                f[s]=max(f[s],f[s^1<<i]+a[c][i]);
        }
    }
    printf("%d\n",f[(1<<N)-1]);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import networkx as nx

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]
     ]

n = len(a)
s = -1
t = -2
g = nx.DiGraph()
for i in range(n):
    for j in range(n):
        g.add_edge(i, j + n, capacity=1, weight=-a[i][j])
for i in range(n):
    g.add_edge(s, i, capacity=1, weight=0)
    g.add_edge(i + n, t, capacity=1, weight=0)
ans = -nx.cost_of_flow(g, nx.max_flow_min_cost(g, s, t))
print(ans)