寻找正整数数组的最大权重子序列？

Question

我试图找到正整数数组的最大权重子序列 - 问题是最终子序列中不允许有相邻成员。

提出了完全相同的问题 这里，MarkusQ给出了一个递归解决方案，如下：

function Max_route(A)
if A's length = 1 
    A[0]
  else
    maximum of
      A[0]+Max_route(A[2...])
      Max_route[1...]

他提供了一个解释，但是任何人都可以帮助我理解他是如何扩展函数的吗？具体来说，他为什么

f[] :- [],0
f [x]     :- [x],x
f [a,b]   :- if a > b then [a],a else [b],b
f [a,b,t] :- 
    ft = f t
    fbt = f [b|t]
    if a + ft.sum > fbt.sum
        [a|ft.path],a+ft.sum
    else
      fbt

将 f[] 扩展为 [],0？另外他的解决方案如何考虑非相邻成员？

我有一些基于这个算法的 C++ 代码，如果有人想看的话我可以发布这些代码，但我就是无法理解它为什么会起作用。

==========对于任何感兴趣的人 - C++ 代码 ==============

我应该补充一点，整数数组将被视为循环列表，因此任何包含第一个元素的序列都不能包含最后一个元素。

int memo[55][55];

int solve(int s, int e)
{
    if( s>e ) return 0;
    int &ret=memo[s][e];
    if(ret!=-1)
    {
        return ret;
    }
    ret=max(solve(s+1,e), solve(s+2,e)+a[s]);
    return ret;
}

class Sequence
{
    public:
    int maxSequence(vector <int> s)
    {
            memset(memo,-1);
            int n = s.size();
            for(int i=0; i<n; i++)
                a[i]=s[i];
            return max(solve(0,n-2),solve(1,n-1));
        }
};

Answer 1

我不太明白那个伪代码，所以如果这没有帮助，请发布 C++ 代码，我会尝试改进它。

我试图找到正整数数组的最大权重子序列 - 问题是最终子序列中不允许有相邻成员。

令 a 为正整数数组。令f[i] = 序列a[0..i] 的最大权重子序列的值。

我们有：

f[0] = a[0]，因为如果只有一个元素，我们就必须采用它。
f[1] = max(a[0], a[1]) 因为你没有相邻元素的限制，所以如果你有两个元素，你只能取其中之一。取最大的一个是有意义的。

现在，通常您会：

f[i > 1] = max(
           f[i - 2] + a[i] <= add a[i] to the largest subsequence of the sequence a[0..i - 2]. We cannot take a[0..i - 1] because otherwise we risk adding an adjacent element.
           f[i - 1] <= don't add the current element to the maximum of a[0..i - 2], instead take the maximum of a[0..i - 1], to which we cannot add a[i].
              )

我认为这种方式比您那里的方式更容易理解。这些方法是等效的，我只是发现对于这个特定问题来说更清晰，因为在这种情况下递归使事情变得更困难，并且伪代码无论哪种方式都可以更清晰。

Answer 2

但你不明白什么？对我来说这似乎很清楚：

• 我们将为给定序列的每个前缀构建最大子序列
• 来​​计算长度 i 的前缀的最大子序列，我们考虑两种可能性：最后一个元素是，或者不在最大子序列中（显然没有其他可能性）。
• 如果存在，我们考虑最后一个元素的值，加上前缀短两个元素的最大子序列的值（因为在这种情况下，我们知道最后一个元素不能出现在最大子序列中，因为 相邻元素规则）
• 如果不是，我们取短一个元素的前缀的最大和的值（如果前缀的最后一个元素不在最大子序列中，则最大子序列必须等于这个和）前面的前缀）
• 我们比较并取两个加号中的最大值

：您需要记住实际的子序列；您需要避免多余的函数调用，因此需要记忆。

为什么他将f[]扩展为[],0？

因为返回值中的第一个表示当前最大子序列，第二个是它的值。空序列的最大子序列为空且值为零。