动态规划-在二维矩阵中找到最大可能的和

Question

在一个2D矩阵中找到最大可能的和，使得如果元素[i][j]被选中，那么下一个元素不能从相同的第i行或第j列中再次被选中。

示例3*3矩阵

, 6.0,, 7.0, 6.0
, 4.56.0,6.75
, 6.05.0,9.0

这里的maximum sum是21，因为6.0(第一行)+6.0(第二行)+9.0(第三行)=21我们不能选择7.0(第一行)+6.75(第二行)+9.0(第三行)，因为6.75和9.0位于同一列。

我知道这是一个动态规划问题。这个的算法是什么?

Answer 1

考虑到您不能重复使用列或行，您的和将是对角线。下面是我对算法的第一次尝试(用伪代码):

our largest known sum is 0.
for(0 to columncount-1)
    sum element[0][column]'s diagonal (i.e. 6.0 + 6.0 + 9.0, then 7.0 + 6.75, then 6.0)
    if it's greater than our largest sum, it becomes the largest sum and we track those elements.
for(1 to rowcount-1)
    sum element[row][0]'s diagonal (i.e. 4.5 + 5.0, then 6.0)
    if it's greater than our largest sum, it becomes the largest sum and we track those elements.

然后你需要从另一个方向重复(即从右向左，然后从上到下)。

我不知道这是否有意义，但这个算法会给你最大的组合，对于任何矩形矩阵

Answer 2

如果我理解正确的话，这本质上是一个可以通过匈牙利算法解决的赋值问题。您只需要通过从全局最大值中减去所有元素或将它们否定来将最大目标转换为最小目标。