algorithm - 从总和重建矩阵

Question

给定每一行和每一列的总和，我想重建一个包含所有正整数元素的矩阵。

a0 a1 a2 .. aN | Σa
b0 b1 b2 .. bN | Σb
.. .  .  .  .. | ..
..  .  .  . .. | ..
z0 z1 z2 .. zN | Σz
---------------+----
Σ0 Σ1 Σ2 .. ΣN |

是否有一种算法可以找到所有 可能的矩阵元素组合，给定行和列的总和。

非常感谢任何引用。

Answer 1

是的。你拥有的是 system of linear equations ，每行一个，每列一个； m*n 个变量和 m+n 个方程。

如何计算(和表示)解决此类系统的解决方案集取决于您的环境。

编辑: 我明白了。对于此问题的大量实例，请参阅 integer programming .

但是如果你的矩阵和行/列的总和很小，那么可以通过backtracking找到所有的解。 .非常高级的伪代码:

function SOLVE(partially filled M) {

    if (M has no empty entries) {

        M is a solution

    } else {

        ij <- one empty position of M
        // in practice, try picking one that reduces the number of
        // iterations of the following loop

        for (each possible value v of M[ij], subject to the constraints) {
            M' <- a copy of M
            M'[ij] = v
            SOLVE(M')
    }
}


M0 <- an empty Matrix of correct size

SOLVE(M0)