Нахождение подпоследовательности максимального веса массива натуральных чисел?

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

Я думаю, что этот путь легче понять, чем то, что у вас есть.Подходы эквивалентны, я просто нахожу это более ясным для этой конкретной проблемы, поскольку рекурсия усложняет ситуацию в этом случае, и псевдокод может быть более ясным в любом случае.

Answer 2

Но что вы НЕ понимаете? Мне кажется вполне понятным:

• мы построим максимальную подпоследовательность для каждого префикса данной последовательности
• для вычисления максимальной подпоследовательности для префикса длины i мы рассмотрим две возможности: либо последний элемент находится, либо не находится в максимальной подпоследовательности (очевидно, что других возможностей нет).
• если он есть, мы рассматриваем значение последнего элемента плюс значение максимальной подпоследовательности префикса на два элемента короче (поскольку в этом случае мы знаем, что последний элемент не может присутствовать в максимальной подпоследовательности из-за смежные элементы правило)
• если это не так, мы берем значение максимальной суммы префикса на один элемент короче (если последний элемент префикса не входит в максимальную подпоследовательность, максимальная подпоследовательность должна быть равна этому и предыдущему префиксу)
• сравниваем и берем максимум из двух

Плюс: вам нужно помнить реальные подпоследовательности; вам нужно избегать лишних вызовов функций, а следовательно, и запоминания.

Почему он расширяется f[] до [],0?

Потому что первое из возвращаемой пары означает текущую максимальную подпоследовательность, а второе - ее значение. Максимальная подпоследовательность пустой последовательности пуста и имеет значение ноль.