通过将行和列乘以-1,使矩阵中的整数之和最大

Question

如果矩阵M的大小m, n超过整数,那么转换它的好算法是什么,所有元素的总和是最大的？

允许的唯一操作是按-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]]

通过"推"减去矩阵的右半部分.

谈到"一半",我也玩过(很多)关于使用矩阵分区的想法,但我无法观察到任何可用的模式.

我尝试过的大多数事情都让我回到原始矩阵,我们可以观察到的这种"雪崩效应"让我发疯.

什么是解决这个问题的好方法？

Answer 1

n 行或 m 列中的任何一个都可以翻转 (-1) 或不翻转 (1)。

这意味着可能性的总数为 2^(n+m)。这意味着存在可以在指数时间内找到的解决方案。对于小矩阵，您可以使用蛮力，搜索翻转和未翻转的列和行的所有可能组合。

然而，您确实需要等到所有内容都应用完毕，否则您将陷入局部最小值。

在这种特定情况下，M 已经是最大和 (27)

import numpy as np

def bit_iter(n):
    for i in xrange(2**(n)):
        bits = []
        for j in xrange(n):
            if i & (2**j) != 0:
                bits.append(1)
            else:
                bits.append(0)
        yield bits

def maximal_sum(M):
    Morig = M.copy()
    n, m = M.shape
    best = None
    for bits in bit_iter(n + m):
        nvec = bits[:n]
        mvec = bits[n:]
        assert(len(nvec) + len(mvec) == len(bits))
        M = Morig.copy()
        for i, v in enumerate(nvec):
            if v == 0:
                M[i, :] *= -1
        for i, v in enumerate(mvec):
            if v == 0:
                M[:, i] *= -1
        if best == None or np.sum(M) > np.sum(best):
            best = M
    return best

M = np.matrix([
    [2,2,2,2],
    [2,2,-2,2],
    [2,2,2,2],
    [2,2,2,1],
])
print maximal_sum(M)
M = np.matrix([
        [1,2],[3,-4]
    ])
print maximal_sum(M)
M = np.matrix([
        [2,-2,2,2],
        [2,2,2,2],
        [2,2,-2,2],
        [2,2,2,2],
        [2,2,2,1],
    ])
print maximal_sum(M)

给出：

[[ 2  2  2  2]
 [ 2  2 -2  2]
 [ 2  2  2  2]
 [ 2  2  2  1]]
[[-1  2]
 [ 3  4]]
[[ 2 -2  2  2]
 [ 2  2  2  2]
 [ 2  2 -2  2]
 [ 2  2  2  2]
 [ 2  2  2  1]]