时间戳

首页 > 解决方案 > 找到具有已知行/列总和和最大单元格值的矩阵的可能解决方案

arrays - 找到具有已知行/列总和和最大单元格值的矩阵的可能解决方案

问题描述

我试图找到一个矩阵的解决方案，我知道行和列的总和以及单元格可以具有的最大值。我想找到限制范围内的可能解决方案。我已经尝试过各种各样的事情，比如构造一个包含所有单元格值的数组并按顺序从每个单元格中挑选，但无论我尝试什么，我总是遇到一个单元格值用完的问题。我还尝试了一种递归算法，但我只能设法得到第一个结果，或者它没有得到任何解决方案。我想我必须用回溯算法来做到这一点？没有把握...

任何帮助或指示将不胜感激。

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

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

标签： arraysalgorithmlinear-programmingsubset-sum

解决方案

如果您听说过线性规划(LP) 及其“表亲”（ILP、MILP），那可能是帮助您高效解决问题的好方法。
线性程序由一组变量（您的矩阵未知数）、约束（最大值、行和列的总和）和一个用于最小化或最大化的目标函数（这里没有）组成。

让我们将 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或Cplex 之类的求解器（但还有更多，例如参见此处）可以非常快地解决此类问题，特别是如果您的解决方案不需要是整数，但可以是浮点数（这使问题变得很大） ，更容易）。它还具有不仅执行速度更快，而且编码更快、更简单的优点。它们具有多种通用编程语言的 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），变量必须都是整数，并且约束和目标函数必须是关于决策变量的线性等式（或不等式）。
然后求解器将作为一个黑匣子工作。它将分析问题，运行可以解决问题的算法，并进行大量优化，然后输出解决方案。

推荐阅读