Динамическое программирование для минимизации суммы квадратов - PullRequest
Новая
       13

Динамическое программирование для минимизации суммы квадратов

3 голосов
/ 15 декабря 2011

У меня есть этот вопрос на практическом экзамене, и я не знаю, как его решить, поэтому я очень боюсь финала. В любом случае, обнаружение, что у этой проблемы есть ответ, помогло бы мне понять динамическое программирование, так что спасибо за чтение:)

Проблема:

Учитывая последовательность из n чисел a1, ..., an (положительных или отрицательных), мы хочу разделить последовательность на блоки, чтобы минимизировать сумму квадраты блочных сумм, с учетом ограничения, что каждый блок содержит не менее 2 и не более 4 элементов. Другими словами, мы хочу найти 1 = i [0]

Моя проблема: определение подзадач. Моя единственная подсказка - постоянно находить минимальные суммы длины от 4 до 2, но что, если останется 1 остаток? Объединяется ли он с существующей группой длины 2 или 3, или расщепляется 4 группы? Не говоря уже о том, чтобы сделать это за O (n) ...

1 Ответ

5 голосов
/ 15 декабря 2011

Подзадача: Найти минимальное число по первым k числам. Вот как вы сводите проблему к уже решенным подзадачам:

Пусть F(k) будет минимальной суммой квадратов при решении для a1, a2, ... ak.

Теперь 

F(2) = (a1+a2)^2
F(3) = (a1+a2+a3)^2
F(4) = min { (a1+a2+a3+a4)^2, (a1+a2)^2 + (a3+a4)^2 }
F(5) = min { (a1+a2+a3)^2 + (a4+a5)^2, (a1+a2)^2 + (a3+a4+a5)^2 }

F(n) = min {
              F(n-2) + (a[n-1]+a[n])^2,
              F(n-3) + (a[n-2]+a[n-1]+a[n])^2,
              F(n-4) + (a[n-3]+a[n-2]+a[n-1]+a[n])^2
       }

Вы можете написать простую функцию, которая вычисляет F (k) для увеличения значений k и сохраняет их в массиве.

...