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

Question

4

我正在寻找一个算法，可以帮助我在一个二维数组中找到非相邻元素的最大和。

对于一维数组，我已经从以下链接中找到了有用的解决方案：

例如，在一个一维数组 {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]

是否有现有算法来解决这个问题？如果我使用另一种数据结构而不是2D数组，是否会有另一种方法来解决这个问题？

- Bryant Khoo

你有四向邻居还是八向的？ - Nico Schertler

抱歉没有明确说明，不允许水平和垂直相邻，但允许对角线相邻。 - Bryant Khoo

这是关于“如何”还是“如何以最佳时间复杂度”？您需要最大值还是近似值就足够了？我们讨论的是多大的二维数组？ - Daniel Jour

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ante · Answer 1

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

我不是整数规划方面的专家。有一个类似（甚至更复杂）的问题，Sascha演示了如何将问题转换为MIP，并展示了求解器的强大功能。