python - 通过排列python中的元素来最小化矩阵中的列总和

Question

我有以下矩阵:

([2, 5, 5, 10]
 [7, 1, 4, 1]
 [1, 3, 3, 9])

如果对列求和，结果是:

[10, 9, 12, 20]

我的目标是确定对不同行中的元素进行排序的最佳方式，以最小化列总和中的最大元素。

例如，一种可能性是:

([2, 5, 5, 10]
 [7, 1, 4, 1]
 [1, 9, 3, 3])

如果对列求和，结果是:

[10, 15, 12, 14]

这是比第一个更好的解决方案。

最简单的方法是检查所有可能的排列，但随着矩阵的增长，这种方法在 python 中变得非常慢。

有什么想法可以更快地做到这一点吗？

Answer 1

这是一个想法:

1. 选择总和最小和最大的 2 列。注意它们的区别，d。
2. 检查两列中的元素。找到具有最大差值绝对值 d' 的行，使得 d' <d 和 d'> 0 .
3. 交换该行中的元素。
4. 重复步骤 1-3，直到步骤 2 不再可行。

示例:给定

([2, 5, 5, 10]
 [7, 1, 4, 1]
 [1, 3, 3, 9])

我们选择总和最小和最大的 2 列。这里我们有最小总和的第 1 列和最大总和的第 3 列。对于这两列，它们的总和之差 d 是 11。

([5, 10]
 [1, 1]
 [3, 9])

现在我们找到最大的差异 d' 使得 d' <d 和 d'> 0，即 9 - 3 = 6。我们现在交换该行中的元素。所以我们有

([2, 5, 5, 10]
 [7, 1, 4, 1]
 [1, 9, 3, 3])

此矩阵的列总和为 [10, 15, 12, 14]

再重复上述过程一次，最终结果如下:

([5, 2, 5, 10]
 [7, 1, 4, 1]
 [1, 9, 3, 3])

此结果矩阵的总和为 [13, 12, 12, 14]。此时，步骤 2 不再可行。所以我们完成了。