最小化最小差值

Question

给定一个正整数的矩阵（非正方形），其中同一行上的所有元素都是可置换的，问题是最小化列的最大和和最小和之间的差异。

例如

  9  5  7        5  7  9      
  9  3  4   ~>   9  4  3
 10  5  9        5 10  9
----------      ----------
 28 13 20       19 21 21

 28-13= 15      21-19= 2

答案是2。

我试着天真地对它进行分类（合并）

Answer 1

不幸的是，通过划分问题的简化，这个问题是NP难的。在分区问题中，你会得到一个数字列表，并想确定是否有办法将这些数字分成两个不相交的组，从而使这些数字的总和相等。

您可以将分区问题的一个实例编码为问题的一个实例，如下所示：创建一个n×2矩阵，其中每行包含集合中的一个数字和一个0。例如，给定集合{1,3,5,7,9}，就可以生成矩阵

1 0
3 0
5 0
7 0
9 0

如果你仔细想想，这里的行排列将返回两列，这两列可以被认为是你将数字划分成的两个集合。如果列之间的最小差值为0，则可以将集合划分为两个相等的子集。如果不是，则无法对集合进行分区。因此，最小化min和max列之间的差异将允许您作为特例解决分区问题。

因为这个问题是NP难的，所以除非P=NP，否则你将无法找到任何简单的多项式时间算法来解决它。不过，你也许可以开发一些启发式来击败蛮力解决方案。

希望这有帮助！