题意理解

已知：

$N \times N$ 矩阵 $\mathbf{B}$

$1 \times N$ 矩阵 $\mathbf{C}$

要求 $1 \times N$ 的 $01$ 矩阵 $\mathbf{A}$，使得 $D = (\mathbf{A} \mathbf{B} - \mathbf{C}) \mathbf{A}^T$ 最大。

其中 $\mathbf{A}^T$ 是 $\mathbf{A}$ 的转置。

公式展开

设 $\mathbf{A} = [a_1, a_2, \dots, a_N]$，$a_i \in {0,1}$。

则： $\mathbf{A} \mathbf{B} = \left[ \sum_{i=1}^N a_i B_{i1}, \sum_{i=1}^N a_i B_{i2}, \dots, \sum_{i=1}^N a_i B_{iN} \right]$

$\mathbf{A} \mathbf{B} - \mathbf{C} = \left[ \sum_{i=1}^N a_i B_{i1} - C_1, \sum_{i=1}^N a_i B_{i2} - C_2, \dots, \sum_{i=1}^N a_i B_{iN} - C_N \right]$

$D = (\mathbf{A} \mathbf{B} - \mathbf{C}) \mathbf{A}^T = \sum_{j=1}^N a_j \left( \sum_{i=1}^N a_i B_{ij} - C_j \right)$

即： $D = \sum_{i=1}^N \sum_{j=1}^N a_i a_j B_{ij} - \sum_{j=1}^N a_j C_j$

问题本质

这是一个二次无约束 0-1 规划问题： $D = \sum_{i,j} a_i a_j B_{ij} - \sum_j a_j C_j$

其中 $a_i \in {0,1}$，$B_{ij} \geq 0$，$C_j \geq 0$。

算法思路

由于 $N \leq 500$，直接枚举 $2^N$ 不可行。

代码采用随机化贪心：

1.初始设所有 $a_i = 1$

2.计算当前 $D$ 值：

先计算 $d_j = \sum_{i=1}^N a_i B_{ij}$（即 $\mathbf{A}\mathbf{B}$ 的结果）

再计算 $D = \sum_{j=1}^N a_j (d_j - C_j)$

3.随机翻转某些位（$a_i \leftarrow 1 - a_i$）

4.重复 $1000$ 次，取最大 $D$

复杂度分析

每次计算 $D$：$O(N^2)$

迭代 $1000$ 次：$O(1000 \times N^2)$

$N = 500$ 时约为 $2.5 \times 10^8$ 操作，可接受

总结

本题是二次 0-1 规划问题，由于 $N$ 较大，采用随机化局部搜索求近似最优解。这种方法在实践中往往能得到不错的结果。