为具有已知 row/column 总和和最大单元格值的矩阵找到可能的解决方案

Question

我正在尝试找到一个矩阵的解，其中我知道行和列的总和以及单元格可以具有的最大值。我想找到在约束范围内的可能解决方案。我已经尝试过各种方法，比如构建所有单元格值的数组并按顺序从每个单元格中挑选，但无论我尝试什么，我总是运行遇到我运行超出单元格值的问题. 我也尝试了一种递归算法，但我只设法得到第一个结果，或者它没有得到任何解决方案。我想我必须用回溯算法来做到这一点？不确定...

如有任何帮助或指点，我们将不胜感激。

行总和 A、B、C，列总和 X、Y、Z 以及每个的最大值？是已知的。所有值都是正整数。

    C1 | C2 | C3 
-----------------
R1 | ? | ?  | ? | A
-----------------
R2 | ? | ?  | ? | B
-----------------
R3 | ? | ?  | ? | C
-----------------
     X | Y | Z

Answer 1

如果您听说过 linear programming (LP) 及其 'cousins' (ILP, MILP)，那可能是帮助您高效解决问题的好方法。
线性程序由一组变量（您的矩阵未知数）、约束（最大值、行和列的总和）和一个用于最小化或最大化的 objective 函数（此处 none）组成。

我们将 x[i][j] 称为您要查找的值。具有以下数据：

NxM 矩阵的维度
max_val[i][j]变量的最大值x[i][j]
row_val[i] 行上值的总和 i
col_val[j] j

列中值的总和

那么可以解决您的问题的一个可能的线性程序是：

// declare variables
int x[N][M] // or eventually float x[N][M] 
// declare constaints
for all i in 1 .. N, j in 1 .. M, x[i][j] <= max_val[i][j]
for all i in 1 .. N, sum[j in 1 .. M](x[i][j]) == row_val[i]
for all j in 1 .. M, sum[i in 1 .. N](x[i][j]) == col_val[j]
// here the objective function is useless, but you still will need one
// for instance, let's minimize the sum of all variables (which is constant, but as I said, the objective function does not have to be useful)
minimize sum[i in 1 .. N](sum[j in 1 .. M](x[i][j]))
// you could also be more explicit about the uselessness of the objective function
// minimize 0

求解器，例如 gurobi or Cplex (but there are much more of them, see here）可以非常快地解决这类问题，特别是如果您的解决方案不需要是整数，但可以是浮点数（这使问题变得非常非常容易） .它还具有不仅执行速度更快，而且编码速度更快、更简单的优点。他们有几种常见编程语言的 API，以方便使用。
例如，您可以合理地期望在不到一分钟的时间内解决此类问题，整数情况下有数十万个变量，实数情况下有数百万个变量。

编辑： 作为对评论的回应，这里有一段 OPL（Cplex 和其他 LP 求解器使用的语言）代码可以解决您的问题。我们考虑 3x3 的情况。

// declare your problem input
int row_val[1..3] = [7, 11, 8];
int col_val[1..3] = [14, 6, 6];
int max_val[1..3][1..3] = [[10, 10, 10], [10, 10, 10], [10, 10, 10]];

// declare your decision variables
dvar int x[1..3][1..3];

// objective function
minimize 0;

// constraints
subject to {
    forall(i in 1..3, j in 1..3) x[i][j] <= max_val[i][j];
    forall(i in 1..3) sum(j in 1..3) x[i][j] == row_val[i];
    forall(j in 1..3) sum(i in 1..3) x[i][j] == col_val[j];
}

LP求解器的概念是你只描述你想解决的问题，然后求解器为你解决。必须根据一组特定的规则来描述问题。在当前情况下（整数线性规划，或 ILP），变量必须都是整数，并且约束和 objective 函数必须是关于决策变量的线性等式（或不等式）。
然后求解器将作为黑匣子工作。它将分析问题，运行算法可以解决它，进行大量优化，并输出解决方案。

Answer 2

正如您在评论中所写，您想提出自己的解决方案，这里有一些指导原则：

使用 Backtrack algorithm 找到解决方案。你的值-space由3*3=9个独立值组成，每个值都在1和maxval[i][j]之间。您的约束将是行和列的总和（它们都必须匹配）

用所有 1 初始化你的 space，然后增加它们，直到它们达到 maxval。仅在该条件涵盖每个值后才评估条件（特别是，在 3 个值之后，您可以评估第一行，在 6 之后评估第二行，在 7 之后评估第一列，在 8 之后评估第二列，在 9 之后评估第三行和第三列）

如果你到达第 9 个，并且所有条件都通过，你就有了解决方案。否则尝试从 1 到 maxval 的值，如果两者都不匹配，则后退。如果迭代第一个值，则无解。

就这些了。

更高级的回溯：

您的移动值只是左上角的2*2=4个值。计算第三列，条件是它必须在 1 和该特定元素的 maxval 之间。定义 [1][1] 元素后，您需要使用列总和计算 [2][2] 索引，并通过行总和验证其值（反之亦然）。与上面相同的处理规则适用：遍历所有可能的值，如果 none 匹配则后退，并且仅在可以应用规则时才检查规则。

这是一种更快的方法，因为您有 5 个绑定变量（底行和右行），只有 4 个未绑定。这些是您的特定规则的优化。不过实现起来有点复杂。

PS：使用1是因为你有正整数。如果您有非负整数，则需要以 0.

开头

为具有已知 row/column 总和和最大单元格值的矩阵找到可能的解决方案

Find possible solutions for a matrix with known row/column sums and maximum cell values

arrays

algorithm

linear-programming

subset-sum