通过在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不再可能.所以我们完成了.