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

Question

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

提出了完全相同的问题 here ，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++ 代码，我会尝试改进它。

I'm tring to find the maximum weight subsequence of an array of positive integers - the catch is that no adjacent members are allowed in the final subsequence.

让 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].
              )

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