0

问题是我有一个填充了 n 个数字的数组。我必须确定最大和，但是，如果将 i 位置的数字加到和中，则数字 i-1 和 i+1 不能相加。

第 n 个数字被认为是在一个循环中。

例如，如果 a 有下一个数组：

{6, 9, 1, 2, 8, 6, 3, 7, 12, 5, 65, 66, 2} 最大和为 99：9 + 8 + 3 +12+ 65 + 2 = 99

4

2 回答 2

1

假设您知道包含数组的第一个元素。然后你可以通过动态规划来解决这个问题：对于 i = 3 到 N - 1，通过考虑包括或不包括元素 i 的选择并查看先前计算的分数，为数组的前 i 个成员制定最佳解决方案第一个 i-1 或 i-2 元素的最佳解决方案，以计算出你可以为 i 元素做的最好的事情。您不需要为 N 个元素计算出最佳值，因为您无法包含最后一个元素，因为您包含了第一个元素，并且前两个元素的分数与第一个元素的分数相同，因为您包含了它.

另一种可能性是不包括第一个元素。但是你可以用同样的方法计算出最好的分数，除了考虑 i = 2 到 N 的可能性。

现在您有了两种可能情况的答案——要么包含第一个元素，要么不包含 - 所以选择最好的。

PS - 如果这不是家庭作业，实际上是否有一个有用的应用程序？它是什么？

于 2012-12-06T05:27:54.933 回答
0

我认为你的问题很有趣，但不想回应，因为你没有表现出你自己的任何努力。

无论如何，由于 mcdowella 已经回答了这个问题，我将尝试详细说明他的答案。

让我们取输入数组：

a = [6, 9, 1, 2, 8, 6, 3, 7, 12, 5, 65, 66, 2]

这个想法是逐步通过这个数组逐步计算两个最佳解决方案。在 stepi中，这两个解是包含的最佳解a[i]和不包含a[i]的最佳解。这是使用上述数组作为输入的该算法的示例运行：

// step = 1
solutions = [6], []

这一步（step - 1）很明显，我们只有数组中的第一个元素。请注意，第一个解决方案组件 ( [6]) 对应于包含a[1]的组件，第二个组件 ( []) 是不包含的组件a[1]。

// step = 2
solutions = [9], [6]

在第二步中，我们添加a[2] = 9到先前未包含的解决方案中a[1]（即第二个组件 - []）。然后我们选择前两个解决方案中最好的作为第二个组件。从这里开始，我们重复相同的过程：

// step = 3
solutions = [6, 1], [9]

// step = 4
solutions = [9, 2], [9]

// step = 5
solutions = [9, 8], [9, 2]

// step = 6
...

您还需要跟踪哪个解决方案（如果有）包含a[1]，因为在最后一步我们不应该添加a[n]到已经包含的解决方案中a[1]。此信息（可以是布尔标志）可以与两个解决方案组件中的每一个相关联，并随着我们进行的每一步更新。

于 2012-12-06T12:36:55.430 回答