Chương trình tìm ma trận hợp lệ cho trước tổng hàng và tổng cột trong Python

Cho mảng rowSum và colSum (giá trị không âm). Tìm ma trận bất kỳ kích thước len(rowSum) x len(colSum) thỏa mãn tổng hàng và tổng cột.

Ví dụ: rowSum=[13,14,12], colSum=[9,13,17] → [[9,4,0],[0,9,5],[0,0,12]].

Giải thuật (Tham lam: chọn min hàng/cột còn lại)

1. Khởi tạo ma trận 0.
2. Lặp cho đến khi đã xử lý hết hàng và cột:
   • Tìm hàng hoặc cột có tổng nhỏ nhất chưa xử lý.
   • Nếu là hàng r: tìm cột c đầu tiên có tổng ≥ min, điền matrix[r][c] = min, trừ min khỏi colSum[c], đánh dấu hàng r done (set = inf).
   • Nếu là cột c: tìm hàng r đầu tiên có tổng ≥ min, điền matrix[r][c] = min, trừ min khỏi rowSum[r], đánh dấu cột c done.

Ví dụ minh họa

def solve(r, c):
    matrix = [[0]*len(c) for _ in range(len(r))]
    visited = set()
    def minimum(r, c):
        min_total = float('inf')
        type_ = ''
        for i in range(len(r)):
            if r[i] < min_total:
                index = i
                type_ = 'row'
                min_total = r[i]
        for i in range(len(c)):
            if c[i] < min_total:
                min_total = c[i]
                type_ = 'col'
                index = i
        if type_ == 'row':
            r[index] = float('inf')
            for i in range(len(c)):
                if c[i] != float('inf') and c[i] >= min_total:
                    c[i] -= min_total
                    matrix[index][i] = min_total
                    break
        if type_ == 'col':
            c[index] = float('inf')
            for i in range(len(r)):
                if r[i] != float('inf') and r[i] >= min_total:
                    r[i] -= min_total
                    matrix[i][index] = min_total
                    break
        visited.add((index, type_))
    while len(visited) != len(r) + len(c):
        minimum(r, c)
    return matrix

rowSum = [13,14,12]
colSum = [9,13,17]
print(solve(rowSum, colSum))

Đầu vào

[13,14,12], [9,13,17]

Đầu ra

[[9, 4, 0], [0, 9, 5], [0, 0, 12]]