java - 如何在 n*n 矩阵中找到每个 a(i, j) 的条目，其中 n<=900 和 a(i,j)=0 或 a(i, j)=1？

Question

假设我基本上给了 n n*n矩阵开头全为零。

并且给出了与每一行和每一列相关联的总和。

例如。 n=4
矩阵:

0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0

给定行总和:2, 2, 1, 1
给定的列总和:2, 0, 2, 2
所以输出矩阵应该是这样的:

0 0 1 1
1 0 0 1
0 0 1 0
1 0 0 0

总有一个解决方案存在。
所以对于 n=4 , 0<=rowsum<=4 and 0<=columnsum<=4

Answer 1

你可以用贪心的方法来解决这个问题。

while not filled:
    find biggest unfilled row:
        fill in putting 1s in columns with largest sums

在您的情况下，您开始于:

    2 2 0 2
  ----------
2 | _ _ _ _
2 | _ _ _ _
1 | _ _ _ _
1 | _ _ _ _

填写我们得到的行之一:

    1 1 0 2
  ----------
2 | _ _ _ _
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

填写另一个:

      1   1
  ----------
  | 1 0 0 1
  | 1 1 0 0
1 | _ _ _ _
1 | _ _ _ _

另外两个也可以类似的填写:

  ----------
  | 1 0 0 1
  | 1 1 0 0
  | 0 1 0 0
  | 0 0 0 1

假设行值的总和与列值的总和匹配，并且 0 <= value <= n对于他们所有人来说，这个程序总是有效的。

更新:正如评论中所指出的，其他方式可能不存在任何解决方案。这可以通过您尝试填充一行而没有足够的列来填充这一事实而被检测到。

但是，如果遇到这样的障碍，则没有解决方案。