贪心算法 0/1 矩阵

Question

我正在准备算法考试，但无法找到解决下一个问题的方法：

输入：正整数 r1，r2....rn 和 c1，c2....cn

输出：一个 n x n 的矩阵 A，其中所有 i 行之和在 A 中为 ri，同时所有 i 列之和在 A 中为 ci。如果这样的矩阵存在，则输出。

考虑以下贪心算法逐行构造 A。假设前 i-1 行已经构造好了，令 aj 为第 i-1 行中第 j 列中的 1 的数量。则在第 i 行中，选择 cj-aj 最大的 ri 列赋值为 1，其余列赋值为 0。即将仍需最多 1 的列赋值为 1。使用交换论证，形式化地证明该算法是正确的。

因此，我尝试了与大多数贪心问题相同的归纳法，假设贪心解法中前 i 行与最优解是相同的，然后尝试更改第 i+1 行，以使其匹配贪心，并证明它不会创建比最优解更劣的解决方案。然后重复这个过程 k-i 次，直到整个解决方案都相似。

尝试失败后，我尝试了相同的思路，但是针对每个坐标进行操作，假设 ij 坐标是第一个不匹配的坐标，但同样失败了。

然后我尝试了另一种方法，假设我有一组贪心步骤，并交换整个步骤（这基本上是第一个思路的相同想法），但我仍然无法找到保证不会创建比最优解更劣的解决方案的方法。

感谢您提前的任何协助。

- user51929

Answer 1

考虑一些输入 r 和 c，以及一个满足它们的矩阵 S。

丢弃 S 中的最后一行内容，得到一个新的矩阵 S(n-1)。如果我们将 S(n-1) 输入贪心算法，并要求其填充这最后一行，那么显然会得到一个满意的解决方案。

现在，再丢弃 S 中最后两行的内容，得到 S(n-2)。由于我们知道存在一个满意的解决方案，因此我们知道不存在 j 满足 c(j) - a(j) > 2，而满足 c(j)-a(j) == 2 的 j 的数量小于等于 r(n-1)。因此，贪心算法将为后者集合中的 j 设置 A[n-1, j] = 1，并为一些 c(j)-a(j) = 1 的其他 j 设置。但是，因为我们知道存在一个满意的解决方案，所以在填充完第 n-1 行后，具有 c(j) - a(j) == 1 的 j 的数量恰好为 r(n)，因此是可满足的。

无论如何，我们可以向下扩展：在 S(n-k-1) 中必须满足以下情况：

• 不存在任何 j 满足 c(j) - a(j) > k+1
• 最多只能有 r(n-k) 个 j 满足 c(j) - a(j) = k+1,
• 且 Sum(c(j) - a(j)) == Sum(r(i), i >= n-k)

因此，在贪心算法处理第 n-k 行后，必须满足以下情况：

• 不存在任何 j 满足 c(j) - a(j) > k
• 最多只能有 r(n-k+1) 个 j 满足 c(j) - a(j) = k,
• 且 Sum(c(j) - a(j)) == Sum(r(i), i >= n-k+1)

因此，当 k = 0 时，不存在任何 j 满足 c(j) - a(j) > 0。

- Andy Jones