二维数组中非相邻元素的最大总和

Question

我试图寻找一种算法来帮助我找到二维数组中非相邻元素的最大总和。

对于一维数组，我发现有用的解决方案从： 1）http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/ 2）https://www.youtube.com/watch?v=UtGtF6nc35g

例如，在一维数组：{3,2，6,2，10} 我将得到最大的总和为19，因为3,6和10是不相邻的。

但是，我无法找到一个可以帮助我的二维数组。我怎样才能找到这个数组中没有水平或垂直相邻元素的整数的最大总和？对角相邻的元素是允许的。

例如：

[3, 2, 6, 2, 10] 
[1, 5, 2, 5, 1] 
[5, 1, 7, 2, 9] 
[3, 9, 1, 8, 2] 

有一个现有的算法来解决这个问题呢？或者，如果我使用另一个数据结构而不是二维数组，它是另一种解决此问题的方法吗？

Answer 1

问题可以表述为maximum-weight independent set或mixed integer linear programming的问题。

要将其转换为最大权重独立集，请创建图形，其中顶点是元素，边是相邻的。

我不擅长整数编程。还有类似的（更复杂的）question，其中sascha展示了如何将问题转化为MIP和解算器的能力。