取一个填充浮点值在0到1之间的n * m矩阵 .
例：
0 0.5 0 0
0 0.5 1 0.4
0.2 1 0.3 0
0 1 0 0
目标是重建此矩阵中的值 .
我无法访问此矩阵，因此我不知道它的任何值 . 有一个计算每个值的函数 calc_value(m,n) . 因此，重构此矩阵的一种简单方法是为每个值调用 calc_value(m,n) .
但是调用这个函数是一个非常昂贵的操作，所以我想尽可能少地调用这个函数 .
我知道矩阵中所有值的总和，以及每个单独行和列中值的总和 . （计算这些总和中的每一个并不比调用 calc_value(m,n) 贵）
Using the row and column sums as additional information, how can I fill all values in the matrix with the least amount of calls to calc_value()?
Is it possible with fewer than O(n*m) calls?
矩阵有一个额外的约束条件可能会有所帮助：每行和每列中的值将是单调的，增加到最大值，然后在该最大值后单调递减 . 所以单行看起来像这样：
0 0.5 0.5 1 1 0.5 0
但不是这样的：
0 1 0 1 0 1
例如不允许多个不同的局部最大值
这是我自己尝试的状态：
到目前为止，我发现了以下不平等 . 对于矩阵M（n，m）的给定值：
M(n,m) <= Min ( sum_of_row_n, sum_of_column_m)
M(n,m) >= sum_of_row_n - sum_of_all_columns_except_m
M(n,m) >= sum_of_column_m - sum_of_all_rows_except_n
但是这些不等式没有提供足够的信息来推导出值M（n，m），除了一些微不足道的情况 .
1 回答
根据您的描述，您的矩阵似乎具有m * n个自由度 . 范围和单调性约束不会降低自由度 . 每个总和（行，列，总）消除一个自由度 - 直到达到（m-1）*（n-1）度 . （由于所有行和的总和以及所有列总和的总和等于总和，因此只能利用这些约束的m n-1） .
所以你可以用给定的信息做的就是：
用calc_value（i，j）计算矩阵元素a_ij，1 <= i <m，1 <= j <n
通过行/列和属性计算每行/列的缺失元素和a_mn