DP - Поиск максимальной суммы массива с определенным набором правил

Question

Это касается конкретного вопроса/проблемы DP, который я получил некоторое время назад, когда меня брали интервью для программы интернатуры SE. Тогда я не мог найти правильное решение, и с тех пор это меня раздражало. Серебряная подкладка - это то, что я понял, что мне нужно работать над методами DP.

Итак, вопрос звучит так: -

Учитывая массив n (т.е. [1, 5, 0] и набор узлов с размером n + 1 (в данном случае, будет 4 узлов), эти узлы нужно быть . устроено таким образом, чтобы найти максимальное значение, которое можно извлечь из этого расположения узлов данных критериев заключаются в следующих: -

• Каждая позиция/индекс в массиве представляет, сколько из других узлов что текущий узел может быть подключен, т. е. первый индекс будет означать, что узел i s подключен к одному другому узлу, второй означает, что узел соединен с двумя другими узлами и так далее и так далее.
• Каждое значение в массиве представляет собой коэффициент усиления, который вы можете извлечь, если узел подключен к одному, двум, трех, ..., (n - 1) другим узлам. Итак, если узел подключен к другому узлу, извлеченное значение (в данном случае) будет равно 1 (согласно указанному выше массиву).
• Расположение этих узлов не может быть круговым. то есть X1 -- X2 -- X3 -- X4 является приемлемым.

Я думаю, несколько примеров поможет в получении более полное представление о предметной области: -

Вход: [1, 5, 0] | Ожидаемый результат: 12 | Ожидаемое расположение узлов: X -- X -- X -- X

Пояснение: - всего 4 узла, вход указывает, что узел даст 1 единицу значения/коэффициента усиления, если он подключен точно к одному другому узлу, 5 единиц, если он напрямую связан с 2 других узла и вообще нет значения/коэффициента усиления, если он напрямую связан с тремя другими узлами. В оптимальной настройке (показано выше) первый и последний узлы получают по 1 единице каждый (каждый из них связан с одним другим узлом), тогда как два узла в середине последовательности дают по 5 единиц узлов. Таким образом, максимальный объем собираемой стоимости/коэффициента усиления составляет 1 + 5 + 5 + 1 = 12.

[0, 0, 0, 0, 50] | Ожидаемый результат: 50 | Ожидаемое расположение узлов: * Подумайте о форме STAR с (n+1)-м узлом в середине, так как коэффициент усиления равен 50, если узел подключен к 5 другим узлам.

[1, 2, 3, 4, 5, 6] | Ожидаемый результат: 12

[3, 9, 6, 15, 9, 21, 15] | Ожидаемый результат: 60

Не стесняйтесь задавать вопросы, если вы действительно не понимаете данную проблему/приведенные примеры, и я попытаюсь изо всех сил прояснить их.

Как я уже сказал, я посреди улучшения себя с проблемами, связанными с DP. Поэтому я не ожидаю, что здесь будет дано полное решение. Я прошу только подсказки/подсказки/отправную точку, с которой я могу работать/с. Алгоритм для обзора тоже будет достаточным!

В принципе, любая помощь будет принята с благодарностью. Заранее спасибо!:)

Answer 1

Это, по сути, похоже на проблему генерации всех отдельных неизоморфных деревьев на вершинах n, а затем нахождение максимального значения, которое можно извлечь из расположения узлов.

Число неизоморфных деревьев порядка n являются , , , , , , , , , , , , , , ... (OEIS A000055), который имеет функцию генерации, но не имеет известной замкнутой формулы.

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

Например, для n = 6:

[1, 2, 2, 2, 2, 1]

[1, 2, 2, 3, 1, 1]

[1 , 2, 3, 1, 2, 1]

[1, 2, 4, 1, 1, 1]

[1, 1, 1, 1, 1, 5]

[ 1, 3 , 1, 1, 3, 1]

Тем не менее, в нашем случае, как [1, 2, 2, 3, 1, 1] и [1, 2, 3, 1, 2, 1] представляют 1(3), 2(2), 3(1) (один узел с тремя вершинами + два узла с двумя вершинами + три узла с одной вершиной). Таким образом, мы можем отбросить все повторяющиеся элементы и генерировать следующие неупорядоченные последовательности в обратном лексикографическом порядке:

[5, 1, 1, 1, 1, 1]

[4, 2, 1, 1, 1 , 1]

[3, 3, 1, 1, 1, 1]

[2, 3, 2, 1, 1, 1]

[2, 2, 2, 2, 1, 1]

Можно сказать:

1. В соединенном дерево с n вершинами (например, выше деревьев), каждая вершина имеет degree по меньшей мере 1 и не более n-1.
2. Размер последовательности S степенных последовательностей дерева совпадает с числом вершин (это очевидно!).
3. Сумма degrees всех вершин: C= 2(n-1) (например, для n = 6, C = 10).

Проблема: Для n узлов, мы имеем n-1 типов узлов, где тип ith элемента имеет степень di и значение vi. Мы пытаемся заполнить последовательность степеней D с общей емкостью C и размером S с выбором элементов максимального значения. Мы можем добавить несколько элементов одного типа к D. Это аналогичная проблема с Integer Knapsack Problem (повторяющимися элементами Разрешенных) с некоторыми ограничениями: общий вес должен быть равен C и количество элементов должно быть равно S.

Пример:n = 4

Мы имеем 3 типов узла (градусы): [1, 2, 3] с заданными значениями: [1, 5, 0] Размера последовательности (ранец) является: 4 и это емкость = 6

DP Решение:

Let us initialize a 3-d array arr[i][j][k] to “unknown” for all i,j,k. 
Value(n,C,S) 
{ 
    if (S == 0) return 0; //No more Space 
    else if (S > C || S * n < C) return INT_MIN; //impossible to fill! 

    if (n == 0) return 0; //No more item 

    if (arr[n][C][S] != unknown) return arr[n][C][S]; 

    if (n > C) result = Value(n-1,C,S); // can’t use nth item 
    else if(n == C && S > 1) result = Value(n-1,C,S); // can't use it, if we do, we won't have enough capacity to fill the spaces 
    else 
    { 
     for(int i = n - 1; i > 0; i--) 
      q = max{q, P[i] + Value(i, C - i, S - 1)} // P[i] = value of a node with a degree of i 

     result = max{q, Value(n - 1, C, S)}; 
    } 
    arr[n][C][S] = result; 
    return result; 
}