给定正整数的矩阵（非正方形），其中同一行上的所有元素都是可置换的，问题是最小化列的最大和最小总和之间的差异 .
例如，
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 .
我试图天真地对它进行排序（将相邻行上的最小值和最大值组合在一起），这样可以得到3x3等小矩阵的正确结果，但是什么可以用于更大的数据（最多约30x30）？是否存在我无法应用的通用解决方案？
1 回答
遗憾的是，这个问题是通过从partition problem减少来实现的 . 在分区问题中，您可以将这些数字拆分为两个不相交的组，以便这些数字的总和相等 .
您可以将分区问题的实例编码为问题的实例，如下所示：创建一个n×2矩阵，其中每行包含集合中的一个数字和0 . 例如，给定集合{1,3， 5,7,9}，你做了矩阵
如果你考虑一下，在这里置换行将返回两列，可以将这两列视为你将数字划分为的两个集合 . 如果列之间的最小差异为0，则可以将该组划分为两个相等的子集 . 如果不是，则无法对该集进行分区 . 因此，最小化最小和最大列之间的差异将允许您作为特殊情况解决分区问题 .
由于这个问题是NP难的，那么除非P = NP，否则你将无法找到任何简单的多项式时间算法来解决它 . 但是，您可能会开发一些启发式方法来击败蛮力解决方案 .
希望这可以帮助！