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

Giả sử chúng ta có hai mảng rowSum và colSum có giá trị không âm trong đó rowSum [i] có tổng các phần tử ở hàng thứ i và colSum [j] có tổng các phần tử trong cột thứ j của ma trận 2D. Chúng tôi phải tìm bất kỳ ma trận nào có giá trị kích thước không âm (kích thước rowSum x colSum size) thỏa mãn các giá trị rowSum và colSum đã cho.

Vì vậy, nếu đầu vào giống như rowSum =[13,14,12] colSum =[9,13,17], thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ma trận:=tạo ma trận trống
• đã thăm:=một tập hợp mới
• Xác định một hàm tối thiểu (). Điều này sẽ mất r, c
• min_total:=infinity
• loại:=chuỗi trống
• đối với tôi trong phạm vi từ 0 đến kích thước của r - 1, thực hiện
  • nếu r [i]
  • index:=i
  • type:='row'
  • min_total:=r [i]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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