问题是找到一个矩阵，该矩阵给出了行和列的总和，并且具有最小数量的非零元素 . 给出两个正整数数组 A[1...N] 和 B[1...M] ， sum(A)=sum(B) . 阵列A和B分别是未知NxM矩阵的行和列和 . 矩阵的元素是非负整数 .
A[1...N]
B[1...M]
sum(A)=sum(B)
这在多项式时间内是否可行？
等效公式 - 创建一个最小尺寸的多组C，可以通过“分解较小的数字”从A和B创建 . 多组C与矩阵中的非零元素相同 . C大小的明显下限和上限是：
max(|A|, |B|) <= |C| <= N+M-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，使得和（Ai）=和（Bi） . 在这种情况下：
|C| <= N + M -1 -k
我认为没有多项式解决方案 . 但以下启发式方法可能有效 .
第1步：排序A和B.
第2步：找到A和B之间的公共元素，并将它们移动到自己的组件中
步骤3：在A中找到两个元素的集合，它们与B中的元素相加并将它们移出 . 对B中与A中的元素求和的两个元素执行相同的操作
第4步： ....
正如您所看到的，随着组件的大小不断增加，它变得越来越难 . 但我不确定是否有更好的解决方案 .
1 回答
如前所述| C | <= N M - 1
但是，假设你可以将A和B分成A1，A2和B1，B2使得sum（A1）= sum（B1）和sum（A2）= sum（B2），约束变小
因此，该问题的目标是将A和B分成最大数量的分量A1，A2，...... Ak和B1，B2，... Bk，使得和（Ai）=和（Bi） . 在这种情况下：
我认为没有多项式解决方案 . 但以下启发式方法可能有效 .
第1步：排序A和B.
第2步：找到A和B之间的公共元素，并将它们移动到自己的组件中
步骤3：在A中找到两个元素的集合，它们与B中的元素相加并将它们移出 . 对B中与A中的元素求和的两个元素执行相同的操作
第4步： ....
正如您所看到的，随着组件的大小不断增加，它变得越来越难 . 但我不确定是否有更好的解决方案 .