algorithm - 由二维数组算法优化组成最大和行解

Question

假设我们有一个二维数组(N 行，M 列)，其中每一列至少有一个具有整数值的非空单元格:

我们可以很容易地组成一个新的单行，其中每个单元格包含从数据数组中相应列中获取的最大值。

解决方案(长度 M)不能有空值。

在这种情况下，解决方案是:

只有一个因素:每列的最大值。

我们想添加另一个因素:组成解决方案的行数最少(比总和值更重要)。

最简单的算法如下:

我 = 1

while (i <= M)
{
    candidates = generateCorrectSolutionsFromAllNLengthRowCombinations(i)

    if ( ! empty(candidates))
    {
        return biggestSumElement(candidates)
    }

    i++
}

该算法返回正确的解决方案，但具有非常高的计算复杂性，这对于较大的矩阵是有问题的。

有没有办法更快地做到这一点？是否在任何地方分析过这个问题(或类似问题)？

问候，

帕特里克

Answer 1

如果您在无序数组中查找值，您永远不知道您要查找的值是否在该数组的最后访问字段中，因此长度为 N 的数组的复杂度为 O(N) 并且不能更小.

加快搜索速度的唯一方法是以某种方式对数组进行排序，或者了解某种模式并基于此跳过数组的某些部分，因为我们确信，解决方案不存在。