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

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, этот алгоритм можно понимать как пример проблемы разбиения .Для простой реализации взгляните на этот код 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, как и ожидалось,Для полного понимания математики, лежащей в основе решения, ознакомьтесь с этими примерами и нажмите ссылку «Сбалансированный раздел».

Answer 2

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

ваша граница W равна 1/2 * sum(elements).

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

Эта проблема на самом деле является проблемой разбиения , которая является частным случаем проблемы суммы подмножеств .

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

Answer 3

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

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