最大化的自基质“非重叠的”数字总和(Maximise sum of “non-overlapping

只是找了一下方向，我认识到，给出的例子是可以使用蛮力迭代来解决，但我正在寻找一个更优雅（即数学？）解决方案，这有可能解决显著大规模的例子（比如20×20或30×30 ）。 这是完全可能的，这不能做，我已经进来了不靠蛮力的方法只有很少的成功...

我有一个矩阵（称为A），它是n×n个。 我想选择从矩阵A点的子集（称为B）的子集将包括n个元素，其中，一个且仅一个元件由每行和从A的每一列采取的输出应提供的溶液（ B），使得该组成B中的元素的总和为最大可能值，给定这些约束条件（例如，25在下面的示例）。 如果B的多个实例被发现（即，不同的解决方案，其提供相同的最大总和）为B中的溶液其具有应选择最大的最小元素。

B还可以是选择矩阵，其是N×N个，但其中只有n个所需的元素为非零。

例如：如果A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B。将

|5 5 5 5 5|

然而，如果A =

|5 4 3|
|4 3 2|
|3 2 1|

B =

|3 3 3|

为B的最小元素是3，其比对于较大

|5 3 1|

要么

|4 4 1|

这也既总和至9

Answer 1:

你的问题是几乎相同的分配问题 ，这可以通过例如将要解决匈牙利算法在多项式时间。

需要注意的是分配问题通常是一个最小化的问题，而是你的矩阵相乘-1和加入一些常数应使该方法适用。 此外，没有正式的领带制动条件，多个最优解的情况下。 然而，该方法产生具有你的最佳总和的溶液。 令m是最低的加数。 通过将所有条目小于或等于m为零，再解决修改您的矩阵。 要么你得到比最后一个更好的总和相同的解决方案。 如果不是这样，以前的解决方案已经是最优的。

Answer 2:

由于马蒂亚斯指出，你应该使用回溯。

1. 找到一个合理的解决方案。 选择从每行最多值，看看它们是不重叠的。 如果不是，则扰乱解决方案的一部分，使得结果变得不重叠的。
2. 限定的部分解决方案的健身。 让我们假设你在每一行反复回升值，你已经从第一k行挑值。 该解决方案的健身等于已经拾起值+最大值之和从剩余行和未选择列
3. 现在递归地开始寻找解决方案。 选择从第一行的值，计算出他们的体能和它们插入到优先级队列。 删除其健身比当前最优解（在步骤1中初始化）下的所有解决方案。 匹克在队列的头部的解决方案，解决方案计算的一个新的水平，并插入他们回到优先级队列。 一旦你已经从所有列和行选择的值，计算总和，如果它比当前最优更高，取代它。

Answer 3:

哎哟。 这个算法是错误的; 没有证据，因为它是错的 ，因此它不可能证明它是正确的。 ;）我离开这里，因为我太执着于将其全部删除，这就是为什么你应该正式证明算法而不是说一个好的示范“这看起来正确的有没有可能的方式，这可能无法正常工作！”

---

我给没有证据这一解决方案，暂且。 我有一个证明草图，但我无法证明最优子这个问题。 无论如何...

问题

给定一个正方形阵列的数字，使得所选择的数字的总和被最大化选择尽可能多的“非重叠的”数字作为可能的。 “非重叠的”是指没有两个数可以是从同一行或同一列中。

算法

• 让A是方形阵列n by n数字。
• 让Aij表示的元件A在i行第j列。
• 让S( i1:i2, j1:j2 )表示用于的正方形子阵列不重叠的数字的总和最佳A含有行的交点i1到i2和列j1到j2 。

然后非重叠数的最佳总和表示为S( 1:n , 1:n )并给出如下：

S( 1:n , 1:n ) = max {  [ S(   2:n , 2:n   ) + A11 ]
                        [ S(   2:n , 1:n-1 ) + A1n ]
                        [ S( 1:n-1 , 2:n   ) + An1 ]
                        [ S( 1:n-1 , 1:n-1 ) + Ann ] }
(recursively)

Note that S( i:i, j:j ) is simply Aij.

也就是说，对于正方形阵列尺寸的最佳总和n可以通过分别计算最佳总和为每个尺寸的四个子阵列来确定n-1 ，然后最大化子阵列的总和和所述元素被“冷落”。

S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

|#      |      |      #|      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |      #|       |#      |

履行

上述递归算法提出了一种递归的解决方案：

def S(A,i1,i2,j1,j2):
    if (i1 == i2) and (j1==j2):
        return A[i1][j1]
    else:
        return max ( S( A, i1+1, i2, j1+1, j2) + A[i1][j1] ],
                     S( A, i1+1, i2, j1, j2-1) + A[i1][j2] ],
                     S( A, i1, i2-1, j1+1, j2) + A[i2][j1] ],
                     S( A, i1, i2-1, j1, j2-1) + A[i2][j2] ], )

请注意，这将会使O(4^n)调用S() 这比阶乘更好的O(n!)的“蛮力”解决方案的时间复杂度，但仍然可怕的表现。

这里要注意的重要一点是，许多电话都重复相同的参数 。 例如，在解决一个3×3阵列，每一2×2阵列被解决了许多倍。

这表明了一个加速两种可能的解决方案：

• 使递归函数S()缓存结果，这样只需要S(A,i1,i2,j1,j2)每进行一次i1,i2,j1,j2 。 这意味着， S()只需要计算O(n^3)结果-所有其他请求从缓存中fufilled。 （这就是所谓的memoising 。）
• 相反，从顶部开始，与大的n*n阵列，并通过连续更小的子问题的工作下来，开始在用尽可能小的子问题的底部，并建立在n*n的情况。 这就是所谓的动态规划 。 这也O(n^3)但它是一个更快的O(n^3)因为你不必缓存命中所有的时间。

动态编程溶液前进有点像：

• 查找所有的1x1子阵的最佳解决方案。 （不重要的。）
• 查找所有的2x2子阵的最佳解决方案。
• 查找所有的3x3子阵的最佳解决方案。
• ...
• 查找所有N-1 * N-1子阵的最佳解决方案。
• 查找完整的N * N子阵的最佳解决方案。

注意这个解决方案：

• 没有证据，但。 我在做这个工作。
• 你会注意到上述算法只给你S()最优的总和 。 它不会告诉你哪些数字实际上弥补了这一数额。 你能在自己的回溯你的路径解决方案的方法添加。
• 上述算法并不能保证像绑物业2,2与1,3将有利于使所有的个体数量尽可能大的被打破（以便2,2胜）。我相信你可以定义max()打破平局有利于最大可能的数字，并会做你想要什么，但我不能证明这一点。

一般注意事项：

动态规划是设计一种用于表现出两个属性的任何问题的快速算法的强大技术：

1. 最优子 ：一个问题可以分解成略小的部分，其中的每一个可以被用作该溶液到原来的问题的一部分。
2. 重叠子问题意味着很少有实际的子问题来解决，并给子问题解决方案被重复使用多次。

如果问题具有最优子，问题分解成略小的问题-比如大小的问题n分解为大小的子问题n-1 -这个问题是可以通过动态规划来解决。

如果你可以分割问题转化为更小的块-说砍大小的问题n成两半，各尺寸的n/2 -这是分而治之 ，而不是动态规划。 分而治之的解决方案一般都非常快-例如二进制搜索将在排序后的数组查找元素O(log n)时间。

Answer 4:

这是关系到N皇后问题，除非你不关心的对角线，并且您已经加权的解决方案。 作为皇后问题，可以通过（多个）回溯解决它。

也就是说，一旦你找到你还记得它的重量的解决方案，标志着soulution为无效，并重新开始。 在（a）中具有最高权重溶液获胜。

文章来源: Maximise sum of “non-overlapping” numbers from matrix