矩陣的最大成本

給你一個 N*M 2D 矩陣，每個單元格包含一個數字，并且沒有兩個單元格具有相同的數字。我們必須從 N 行中的每一行中選擇一個元素，讓選擇的元素為 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
如果我們選擇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

uj5u.com熱心網友回復：

你可以及時解決這個問題O(N log N)，其中N元素的總數。

首先，我們可以定義一個非負整數的值，而與x它所在的行無關。Letmax_at_most(row, x)表示一個函式，它回傳的最大元素row最多為x，如果不存在，則回傳 0。

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

現在，max_at_most是固定行的單調函式，x每行最多只改變長度（行）次，我們可以用它來快速計算它。

查找矩陣中的所有唯一元素，并跟蹤每個元素出現的行索引。對獨特的元素進行排序。現在，如果我們按順序遍歷元素，我們可以及時跟蹤每行中看到的最大元素（以及max_at_most(row, x)所有行的總和）O(1)。

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)

標籤：数组 算法 数学 矩阵 最大化

上一篇：如何優化這個計算數字等于和的n位十六進制數的數量的遞回函式？

下一篇：flask初始化前無法訪問