Алгоритм получения записей таблицы?

Question

Скажем, у меня есть эта таблица неотрицательных записей:

    1   2   3   sum
1   4   5   1   10
2   6   12  7   25
3   0   3   14  17
4   7   2   5   14
sum 17  22  27  66

дано:

1. количество столбцов C и количество строк R
2. две суммы записей (сумма каждой строки и сумма каждого столбца)
3. и общее количество (66 в этом примере)

Цель состоит в том, чтобы произвести записи таблицы (внутренние ячейки; не те же самые., Но сумма должна быть равна заданным для каждой строки и каждого столбца), все записи должны быть положительными значениями.

Любой псевдокод, чтобы сделать это?

Answer 1

Попробуйте мой псевдокод. Это правило называется чем-то вроде "Правило северо-западного угла" (я не могу найти настоящее название этого правила в вики)

row = 1
col = 1

while (col <= C && row <= R)
  Matrix[col, row] = Min(colsum[col], rowsum[row])
  colsum[col] = colsum[col] - Matrix[col, row]
  rowsum[row] = rowsum[row] - Matrix[col, row]
  while (col <= C && colsum[col] == 0) col++
  while (row <= R && rowsum[row] == 0) row++

Print Matrix;

Answer 2

Перебирайте ячейки таблицы в любом порядке. На каждом шаге укажите наибольшее число, которое по-прежнему разрешено двумя ограничениями суммы.

Например, если мы идем строка за строкой:

10  0  0
 7 18  0
 0  4 13
 0  0 14

Answer 3

Создать набор линейных уравнений, таких как; X+ Y + .. = сумма

Для каждой строки и каждого столбца. И решить с помощью стандартных методов решения линейных уравнений.