โปรแกรมหาเมทริกซ์ที่ถูกต้องจากผลรวมแถวและคอลัมน์ใน Python

ปัญหา

มี rowSum และ colSum หาเมทริกซ์ขนาด (len(rowSum) x len(colSum)) ค่าไม่ติดลบ ที่ผลรวมแถวและคอลัมน์ตรงตามที่กำหนด

ตัวอย่าง

rowSum=[13,14,12], colSum=[9,13,17] → เมทริกซ์ [[9,4,0],[0,9,5],[0,0,12]]

ขั้นตอนการแก้ปัญหา

1. matrix := zeros, visited := set()
2. ฟังก์ชัน minimum(r, c):
   • หา min_total และ type ('row' หรือ 'col') ที่มีค่าน้อยที่สุดใน r,c ที่ยังไม่ infinity
   • ถ้า type == 'row': ตั้ง r[index] = inf, หา c[i] >= min_total แรก ลบ min_total ออกจาก c[i], ตั้ง matrix[index][i] = min_total
   • ถ้า type == 'col': ตั้ง c[index] = inf, หา r[i] >= min_total แรก ลบ min_total ออกจาก r[i], ตั้ง matrix[i][index] = min_total
   • เพิ่ม (index, type) เข้า visited
3. วนจน len(visited) == len(r) + len(c)
4. คืน matrix

การนำไปใช้งาน (Python)

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))

อินพุต

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

เอาต์พุต

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