问题是我有一个填充了 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
假设您知道包含数组的第一个元素。然后你可以通过动态规划来解决这个问题:对于 i = 3 到 N - 1,通过考虑包括或不包括元素 i 的选择并查看先前计算的分数,为数组的前 i 个成员制定最佳解决方案第一个 i-1 或 i-2 元素的最佳解决方案,以计算出你可以为 i 元素做的最好的事情。您不需要为 N 个元素计算出最佳值,因为您无法包含最后一个元素,因为您包含了第一个元素,并且前两个元素的分数与第一个元素的分数相同,因为您包含了它.
另一种可能性是不包括第一个元素。但是你可以用同样的方法计算出最好的分数,除了考虑 i = 2 到 N 的可能性。
现在您有了两种可能情况的答案——要么包含第一个元素,要么不包含 - 所以选择最好的。
PS - 如果这不是家庭作业,实际上是否有一个有用的应用程序?它是什么?
我认为你的问题很有趣,但不想回应,因为你没有表现出你自己的任何努力。
无论如何,由于 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]
。此信息(可以是布尔标志)可以与两个解决方案组件中的每一个相关联,并随着我们进行的每一步更新。