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

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

完全相同的问题被询问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));
        }
};

最佳答案

我不太了解该伪代码，因此如果没有帮助，请发布C++代码，我将尝试对其进行改进。



令a为正整数数组。让f[i] = value of the maximum weight subsequence of the sequence 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].
              )

我认为这种方式比您所拥有的更容易理解。这些方法是等效的，我只是在这个特定问题上发现了更清晰的方法，因为在这种情况下，递归使事情变得更加困难，并且伪代码可能更清晰。

关于c++ - 寻找正整数数组的最大权重子序列？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2891525/