algorithm - 查找具有最少数量非零元素的矩阵以满足行和列总和

Question

问题是找到一个矩阵，该矩阵具有给定的行和列总和，并且具有最小数量的非零元素。给定两个正整数数组 A[1...N] 和 B[1...M]，sum(A)=sum(B) 。数组 A 和 B 分别是未知 NxM 矩阵的行和列之和。矩阵的元素是非负整数。

这在多项式时间内可能吗？

等效公式 - 创建一个最小尺寸的多集 C，它可以通过“将数字分解成更小的部分”从 A 和 B 创建。多重集 C 与矩阵中的非零元素相同。 C 大小的明显下限和上限是:

max(|A|, |B|) <= |C| <= N+M-1

Answer 1

正如你之前提到的|C| <= N + M - 1

但是，假设您可以将 A 和 B 拆分为 A1、A2 和 B1、B2，使得 sum(A1) = sum(B1) 和 sum(A2) = sum(B2)，约束变小

|C| <= (|A1| + |B1| -1) + (|A2| + |B2| -1)
    <= N + M - 2

因此，该问题的目标是将 A 和 B 拆分为最大数量的分量 A1、A2、... Ak 和 B1、B2、... Bk，使得 sum(Ai) = sum(Bi)。在这种情况下:

 |C| <= N + M -1 -k

我认为对此没有多项式解。但以下启发式方法可能会奏效。

第 1 步:对 A 和 B 进行排序

第 2 步:找到 A 和 B 之间的公共(public)元素并将它们移出到它们自己的组件中

第 3 步:找到 A 中两个元素的集合，这些元素和 B 中的一个元素相加，并将它们移出。对 B 中的两个元素执行相同的操作，它们总和为 A 中的一个元素

第 4 步:....

如您所见，随着组件的大小不断增加，它变得越来越难。但我不确定是否有更好的解决方案。