矩阵的最大成本

Question

给你一个 N*M 的二维矩阵，每个单元格包含一个数字，并且没有两个单元格具有相同的数字。我们必须从 N 行的每一行中 select 一个元素，设 selected 元素为 c1,c2,...cN。
Matrix 的成本定义为 - sum of (ci-sj)(1<=i,j<=N) 其中 sj 表示第 j 行中最大的元素 <=ci，如果不存在这样的 sj，则sj=0.

我们必须找到矩阵的最大可能成本。

例如：-
如果 N=M=3 且矩阵 = [[4,3,2], [6,1,5], [8,9,7]]
现在 c1 的值可以是 4,3 或 2，c2 的值可以是 6,1 或 5，c3 的值可以是 8,9 或 7
如果我们 select c1=4, c2=6 和 c3=9

c1 的成本 = (4-4)+(4-1)+(4-0)=7，这里 s1 = 4（最大元素 <=c1=第一行 4), s2 = 1, s3 = 0(因为第三行没有元素 <=c3=9)
同样，c2的成本=(6-4)+(6-6)+(6-0)=8
c3 的成本 = (9-4)+(9-6)+(9-9) = 8
总成本 = 7+8+8 = 23
这是我们可以从 c1,c2,c3 的任意值得到的最大分数。

另一个例子：-
如果 Matrix = [[2,22,28,30],[21,5,14,4],[20,6,15,23]] 那么最大成本将为 60.

我尝试从每行中选择最大元素作为 ci，但这不起作用。谁能告诉我们如何处理和解决这个问题？

编辑：我已经尝试了很长时间来编码和理解这一点，但我无法成功地做到这一点，这是我到目前为止能够编码的，这通过了一些案例，但失败了一些。

def solve(matrix):
    N = len(matrix)
    M = len(matrix[1])
    
    i = 0
    totalcost = 0
    for row in matrix:
        itotalcost = 0
        for ci in row:         
            icost = 0
            totalicost = 0
            for k in range(0, N):
                if k != i:
                    idx = 0
                    sj = 0
                    isj = 0
                    for idx in range(0, M):
                        isj = matrix[k][idx]
                        if isj <= ci and isj > sj:
                            sj = isj
                    icost = ci - sj
                    totalicost += icost
                    #print("ci=", ci, "sj", sj, "icost=", icost)
            if itotalcost < totalicost:
                itotalcost = totalicost
        i += 1
        #print("itotalcost=", itotalcost)
        totalcost += itotalcost
    return totalcost

Answer 1

你可以在 O(N log N) 时间内解决这个问题，其中 N 是元素的总数。

首先，我们可以定义一个非负整数 x 的值，与它所在的行无关。令 max_at_most(row, x) 表示返回 row 中最大元素的函数，即至多 x，如果存在 none，则为 0。

然后： value(x) = sum over all rows R of: { x - max_at_most(R, x) }

现在，max_at_most是固定行的x的单调函数，每行最多只改变length(row)次，我们可以用它来快速计算.

查找矩阵中的所有唯一元素，并跟踪每个元素出现的行索引。对唯一元素进行排序。现在，如果我们按顺序遍历元素，我们可以在 O(1) 时间内跟踪每行中看到的最大元素（以及所有行的 max_at_most(row, x) 的总和）。

def max_matrix_value(matrix: List[List[int]]) -> int:
    """Maximize the sum over all rows i, j, of (c_i - f(j, c_i)})
    where c_i must be an element of row i and f(j, c_i) is the largest
    element of row j less than or equal to c_i, or 0 if none exists."""

    num_rows = len(matrix)

    elem_to_indices = defaultdict(list)
    for index, row in enumerate(matrix):
        for elem in row:
            elem_to_indices[elem].append(index)

    current_max_element = [0] * num_rows
    current_max_sum = 0

    max_value_by_row = [0] * num_rows

    for element in sorted(elem_to_indices):

        # Update maximum element seen in each row
        for index in elem_to_indices[element]:
            difference = element - current_max_element[index]
            current_max_sum += difference
            current_max_element[index] = element

        max_value_for_element = element * num_rows - current_max_sum

        # Update maximum value achieved by row, if we have a new record
        for index in elem_to_indices[element]:
            max_value_by_row[index] = max(max_value_by_row[index],
                                          max_value_for_element)

    return sum(max_value_by_row)

矩阵的最大成本

Maximum cost of Matrix

arrays

algorithm

math

matrix

maximize