Как смоделировать проблему разбиения как проблему динамического программирования?

Question

Я не могу понять, как эту проблему с разделами можно рассматривать как проблему динамического программирования.

У меня есть следующие сомнения:

1) Это не проблема оптимизации (илиЯ не могу видеть), тогда почему мы применяем подход DP к нему?

2) Задачи DP удовлетворяют 2 свойствам:

1. Перекрывающиеся подзадачи

2. Оптимальная подструктура

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

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

arr [] = {1, 5, 11, 5}

Вывод: true

Массив может быть разделен как{1, 5, 5} и {11}

arr [] = {1, 5, 3}

Вывод: false

Массив нельзя разбить на равныенаборы сумм.

Answer 1

Задача NP-Complete, но для меньших ограничений она решаема с помощью динамического программирования.

Отношение повторения будет следующим:

f (index, sum) = f(index, sum + arr [index]) или f (index + 1, sum - arr [index])

и для базового случая:

if(index >= arraySize) {
    if ( sum == 0 ) 
        return true;
    else
       return false;

}

Времясложность и сложность памяти этой функции: O (arraySize * MaximumSum) .Поэтому, если arraySize * MaximumSum достаточно мало, проблема решается с помощью динамического программирования.