Как найти алгоритм: задан массив целых чисел, какова максимальная сумма подмножества целых чисел, такого что

Пусть у вас есть массив A {Ai, 1 <= i <= n }

F(i) - Максимальная сумма подмассива Aj { 1 <= j <= i }, тогда

F(0) = 0 - пустой подмассив

F(1) = A(1) - только первый элемент

F(i) = max(F(i-2) + A(i), F(i-1)) , 2 <= i <= n

F(n) - ответ

Реализация С++:

int GetMaximumSubarraySum(const vector<int>& a)
{
    // note that vector a have 1-based index
    vector<int> v(a.size());
    v[0] = 0;
    v[1] = a[1];
    for(int i =2; i < a.size(); i++)
        v[i] = max(v[i-2] + a[i], v[i-1]);

    return v.back();
}

Пояснение:

Во-первых, основная идея заключается в использовании динамического программирования. Мы пытаемся решить задачу для массива с N элементом, используя известный ответ для массива с N-1 и N-2 первыми элементами. Если N = 0, ответ 0, а если N = 1, ответ A[1]. Ясно. Для N >= 2 у нас есть 2 разных способа:

1. Используйте элемент A[N],, тогда ответ будет A[N] + F[N-2] (поскольку мы не можем использовать элемент A[N-1], а F[N-2] является лучшим решением для подмассива 1..N-2, нас не волнует, используется элемент F[N-2] или нет, это просто лучшее решение для подмассива 1..N-2.

2. Не используйте элемент A[N], тогда ответ будет F[N-1] (потому что мы можем использовать элемент A[N-1], а F[N-1] — лучшее решение для подмассива 1..N-1, также нас не волнует, используется элемент F[N-1] или нет.

Итак, нам нужно получить максимум из этих двух ситуаций. Для решения задачи нужно посчитать F[N] в порядке возрастания и запомнить ответы.

Посмотрим на вашем примере:

[12, 8, 9, 10]

F[0] = 0

F[1] = 12 - использовать 1-й элемент

F[2] = max(F[0]+A[2], F[1]) = max(8, 12) = 12 - использовать 1-й элемент

F[3] = max(F[1]+A[3], F[2]) = max(21, 12) = 21 - использовать 1-й, 3-й элемент

F[4] = max(F[2]+A[4], F[3]) = max(22, 21) = 22 - использовать 1-й, 4-й элемент

Ответ F[4] = 22.

Единственный известный мне одинаково успешный мыслительный процесс — это увидеть проблему раньше. Глядя на ваш вопрос, моей первой мыслью было: «Мне нужно максимизировать сумму с учетом того, что кажется набором довольно простых логических ограничений». В Knuth Vol 4A, раздел 7.1.4 Алгоритм B, Кнут описывает, как решить такую ​​проблему, если ограничения могут быть выражены в виде http://en.wikipedia.org/wiki/Binary_decision_diagram управляемого размера. Если у вас уже есть пакет BDD, вы можете решить целый класс проблем этого типа, просто создав BDD, описывающий ваши конкретные ограничения.

Второй моей мыслью было отметить, что позже в том же разделе Кнут показывает связи между BDD и линейными сетями булевой логики. Учитывая это, для вашей проблемы должно быть приемлемое решение динамического программирования. Если вы ищете общую методологию для изучения, динамическое программирование — довольно хороший кандидат. В этом случае это, кажется, приводит к алгоритму, очень похожему на представленный Иваном Бенко, хотя он, кажется, работает в соответствии с предположением, поддерживаемым вашими примерными данными, что все целые числа >= 0, и это может работать для общего целые числа с еще несколькими операторами if.

Думайте рекурсивно: лучший результат - максимальный из случаев - использовать первый элемент (первый в ветке рекурсии) или не использовать его в сумме.

Лучший (i) = Макс (A [i] + Лучший (i + 2), Лучший (i + 1))

Вот решение, известное как алогитм Кадане.

Algorithm 1 Kadane’s algorithm
   M ← 0, t ← 0
   i ← 1
   for j ← 1 to n do          
      t ← t + a[j]
      if t > M then M ← t, (x1 , x2 ) ← (i, j)           
      if t ≤ 0 then t ← 0, i ← j + 1// reset the accumulation
   end for
   output M , (x1 , x2 )