有一个大小为m,n
的整数矩阵M
,如何将其转换为使所有元素之和最大的算法?
唯一允许的操作是按列或行乘以-1
。可以执行任意多次此类操作。
粗略的总体思路:我的想法是将每个负数的负号移动到值最小的正数上,以使负数对总和的影响最小。
让我们举个例子:
import numpy as np
M = np.matrix([
[2,2,2,2],
[2,2,-2,2],
[2,2,2,2],
[2,2,2,1],
])
def invert_at(M, n, m):
M[n,:] *= -1
M[:,m] *= -1
我已经尝试过通过从负数元素到最小数字构建最短路径并沿途
invert_at
每个单元格来实现此目标。首先包括起始和结束单元格:
invert_at(M, 1, 2) # start
invert_at(M, 2, 2)
invert_at(M, 3, 2)
invert_at(M, 3, 3) # end
我最终得到了:
[[ 2 2 -2 -2]
[-2 -2 -2 2]
[-2 -2 2 2]
[ 2 2 -2 -1]]
这看起来很有趣。它将负数推到右下角的-1,但也影响到其他区域。现在,如果我在起始和结束位置再次反转(即-1 * -1 = 1
),因此首先略过第一个和最后一个单元格,我最终得到:
[[ 2 2 2 2]
[ 2 2 -2 2]
[-2 -2 -2 -2]
[-2 -2 -2 -1]]
就外观而言,考虑到我的需求,哪个更好?
[[ 2 2 2 2]
[ 2 2 2 2]
[ 2 2 2 2]
[ 2 2 2 -1]]
通过将负数“推向”矩阵的右半部分来解决问题。
谈到“半”,我也曾经尝试过使用矩阵的分区,但是我没有观察到任何可用的模式。
我尝试过的大多数方法都将我带回了原始矩阵,而这种“雪崩效应”让我感到疯狂。
解决这个问题的好方法是什么?
MxN
(M,N> 1)的灯泡网格(最初关闭),每行和每列都有一个开关,确定一种算法,以产生只有一个灯泡打开的网格。我记得有一个聪明的技巧,可以打开和关闭行和列的正确交叉点,以逐个关闭所有灯泡,但它现在想不起来了... - Bakuriu