algorithm - 二维房屋强盗算法

Question

这似乎是 LeetCode 盗屋问题的变体，但我发现它更难解决:

在 NxN 网格上布置了一些房屋。众所周知，每个房子都包含一定数量的贵重元素。强盗的任务是尽可能多地抢劫房屋，以最大限度地增加战利品的数量。然而，这里有一个安全系统，如果你抢劫两间相邻的房子(左边、右边、上面和下面)，警报就会响起。找出强盗可以抢劫的最大战利品。

      Houses   :  alignment
     10 20 10      0  1  0
     20 40 20  =>  1  0  1
     10 20 10      0  1  0

   This alignment results in the maximum of 80.

我从 https://shanzi.gitbooks.io/algorithm-notes/problem_solutions/house_robber.html 学习了如何使用动态规划解决单排房屋的最佳选择问题:

public class HouseRobber {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = nums[i];
            // Do not need to check k < i - 3. 
            for (int j = 2; i - j >= 0 && j <= 3; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + nums[i]);
            }
            max = Math.max(dp[i], max);
        }

        return max;
    }
}

但是一旦我选择了一行的最佳选择，它可能与该行上方和下方各行的最佳选择不一致。即使我找到了两行的最佳组合，下一行可能比这两行的总和更有值(value)，并且需要再次调整，等等。

这很困难，因为与单排房屋相比，要考虑的变量要多得多，而且还可能有不止一种最佳排列方式可以让强盗获得最大的战利品(如上例)。

我确实发现了一个用 Python 编写的似乎很糟糕的解决方案，但由于我只了解基于 C 的语言(Java、C#、C++)，所以我无法从中获益。谁能帮我解决问题或至少提供一些建议？

感谢您的宝贵时间!

Answer 1

我浏览了 python你提到的代码。使用流程的解决方案对我来说看起来完全错误。没有从源到汇的路径具有有限的权重。该解决方案基本上像棋盘一样为网格着色，并选择所有黑色方 block 或所有白色方 block 。在以下情况下这不是最佳选择:

1     500
300   1
1000  300

最好选择 1000 和 500，但该解决方案将选择 300+300+500。

动态规划的解是指数级的。 我的数学知识不够，无法理解 LP 解决方案。

很抱歉没有回答您的问题。