寻找满足行和列和的非零元素个数最小的矩阵

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

正如您前面所提到的，\x{e76f}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之间的共同元素，并将它们移动到它们自己的组件中

步骤3:在A中找到两个元素的集合，这些元素之和为B中的一个元素，然后将它们移出。对B中两个和A中一个元素的元素执行相同的操作

第四步：.

正如您所看到的，随着组件的大小不断增加，它变得越来越困难。但我不知道是否有更好的解决办法。