arrays - テーブルのエントリを取得するアルゴリズム？

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. 2つの合計エントリ（各行の合計と各列の合計）
3. および合計（この例では66）

目標は、テーブルのエントリ（内側のセル。同じセルではありません。ただし、合計は各行および各列の指定されたセルと等しくなければなりません）を生成することです。すべてのエントリは正の値である必要があります。

それを行うための擬似コードはありますか？

Answer 1

テーブルセルを好きな順序で繰り返します。各ステップで、2つの合計制約によってまだ許可されている最大数をそこに配置します。

たとえば、行ごとに移動する場合：

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

Answer 2

私の擬似コードを試してください。このルールは「北西コーナーのルール」のような名前です（このルールの本名はwikiで見つかりません）

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 3

次のような線形方程式のセットを作成します。X + Y +..=合計

各行と各列。そして、線形方程式を解く標準的な方法を使用して解きます。