algorithm - 0\1 的贪心算法矩阵

Question

我正在为算法考试而学习，但我找不到解决下一个问题的方法:

输入:正整数 r1,r2....rn 和 c1,c2....cn

输出:具有 0/1 个条目的 n × n 矩阵 A，使得对于所有 i 中第 i 行的总和如果存在这样的矩阵，则 A 为 ri，A 中第 i 列的总和为 ci。考虑以下逐行构造 A 的贪心算法。假设第一个i-1 行已构建。令 aj 为前 i-1 行中第 j 列中 1 的个数。具有最大 cj-aj 的 ri 列在 row 中分配为 1，其余列的列分配了 0。也就是说，仍然需要最多 1 的列被赋予 1。使用交换参数正式证明该算法是正确的。

因此，对于我遇到的大多数贪心问题，我尝试做的是将其总结为归纳法，假设贪心解和最优解中直到第 i 行的行是相同的，然后尝试更改第 i+1 行，使其与贪心匹配并证明它不会创建次优解到最优给定。然后保持 k-i 次迭代，直到整个解决方案相似。

在尝试失败后，我仅针对每个坐标尝试了相同的想法，假设 ij 坐标是第一个不匹配的坐标，但再次失败。

然后我尝试了一种不同的方法，假设我在贪心算法中有一组步骤并交换算法的整个步骤(这与第一个基本相同的想法)但我仍然没有设法找到一种方法保证我没有创建不太理想的解决方案。

在此先感谢您的帮助。

Answer 1

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

丢弃S中最后一行的内容，得到一个新的矩阵S(n-1)。如果我们将 S(n-1) 提供给贪婪算法并要求它填写最后一行，它显然会得到一个令人满意的解决方案。

好吧，现在丢掉 S 中最后 两 行的内容，得到 S(n-2)。因为我们知道存在一个令人满意的解决方案，所以我们知道不存在 j 使得 c(j) - a(j) > 2，并且 的数量j 使得 c(j)-a(j) == 2 小于或等于 r(n-1)。因此，贪心算法将为后一组 j 设置 A[n-1, j] = 1，以及其他一些 j 其中 c(j)-a(j) = 1。但是因为我们知道有一个令人满意的解决方案，它必须是 n 之后 c(j) - a(j) == 1 的 j 的数量-1填充的第 1 行恰好是 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