我正在准备算法考试,但无法找到解决下一个问题的方法:
输入:正整数 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 坐标是第一个不匹配的坐标,但同样失败了。
然后我尝试了另一种方法,假设我有一组贪心步骤,并交换整个步骤(这基本上是第一个思路的相同想法),但我仍然无法找到保证不会创建比最优解更劣的解决方案的方法。
感谢您提前的任何协助。
输入:正整数 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 坐标是第一个不匹配的坐标,但同样失败了。
然后我尝试了另一种方法,假设我有一组贪心步骤,并交换整个步骤(这基本上是第一个思路的相同想法),但我仍然无法找到保证不会创建比最优解更劣的解决方案的方法。
感谢您提前的任何协助。