Проблемы с динамическим программированием

Question

У меня возникли трудности с пониманием динамического программирования, поэтому я решил решить некоторые проблемы. Я знаю основные динамические алгоритмы, такие как самая длинная общая подпоследовательность, проблема с рюкзаком, но я их знаю, потому что я их читаю, но я не могу придумать что-то самостоятельно :-(

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

in1:... 10 3 5 4; out1: 2

in2 : 4 11 5 5 5; out2: 0

in3: 10 50 60 65 90 100; out3: 5

описание для 3-го: 5 = | 10 + 50 + 60 + 65-90-100 |

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

Answer 1

Как указывалось amit, этот алгоритм можно понимать как экземпляр partition problem. Для простой реализации взглянуть на этот Python код:

def partition(A): 
    n = len(A) 
    if n == 0: 
     return 0 
    k, s = max(A), sum(A)/2.0 
    table = [0 if x else 1 for x in xrange(n*k)] 
    for i in xrange(n): 
     for j in xrange(n*k-1, -1, -1): 
      if table[j-A[i]] > table[j]: 
       table[j] = 1 
    minVal, minIdx = float('+inf'), -1 
    for j in xrange(int(s)+1): 
     if table[j] and s-j < minVal: 
      minVal, minIdx = s-j, j 
    return int(2*minVal) 

При вызове с одним из входов в вопросе:

partition([10, 50, 60, 65, 90, 100]) 

Он вернется 5, как и ожидалось. Чтобы полностью понять математику за решением, посмотрите на это examples и нажмите ссылку «Balanced Partition».

Answer 2

Это та же проблема, как и в Tug Of War, без ограничения сбалансированных размеров команды (которая не имеет отношения): http://acm.uva.es/p/v100/10032.html

Я решил эту проблему с сверху вниз. Он работает над ограничением, что существует верхний предел числа. У вас есть верхний предел или числа без ограничений? Если они не ограничены, я не вижу, как это можно решить с помощью динамического программирования.

Answer 3

Рюкзак здесь weight = value = number для каждого элемента.

Ваши обязательства W является 1/2 * sum(elements).

Идея - вы хотите максимизировать количество чисел, которые вы «выбираете», не проходя пределов 1/2 * sum(elements), что является точно рюкзаком с value=weight.

Эта проблема на самом деле partition problem, которая является частным случаем subset sum problem.

Проблема раздела говорит: «Можно ли получить подмножество элементов, суммирующих ровно половину?»
Вывод к вашей проблеме отсюда прост - если есть, возьмите их как +, а те, которые вы не приняли за -, и получите out = 0. [наоборот работает одинаково]. Таким образом, описанная вами проблема - это оптимизация проблемы раздела.