Каков эффективный алгоритм динамического программирования для минимизации общей стоимости массива без удаления двух соседних элементов?

Я пытаюсь разработать эффективный алгоритм динамического программирования, который, учитывая массив целых чисел длины n и ограничение количества целых чисел которое можно удалить k, минимизирует общую стоимость (т. е. сумму целых чисел) массива, удаляя из него элементы так, чтобы никакие два последовательных элемента в массиве не удалялись. Я думаю, что это в основном то же самое, что и максимизация стоимости общего количества целых чисел, которые я удалил, но я не совсем уверен. Откровенно говоря, я полностью застрял на шаге повторения алгоритма.

Изменить: количество удаляемых элементов может быть меньше или равно введенному значению k.


arrays algorithm dynamic-programming minimization
person iheartcoding124    schedule 06.11.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

Повторение:

MaxDel(i, m) = Max(A[i] + MaxDel(i+2, m+1), MaxDel(i+1, m)) if (m < k and i < N) else 0

Описание: Мы можем удалить i-й элемент, в этом случае мы должны опустить i+1 и перейти к i+2, или мы можем опустить i-й и перейти к следующему. Остановиться, когда у нас будет удалено k элементов или индекс выйдет за пределы массива.

person MBo    schedule 06.11.2020
comment
Будет ли это работать, если k = 2 и у нас есть массив [10,6,7,10,8,6,9]? Я думаю, что он просто удалит 10 и 7, но он должен удалить обе 10, чтобы сделать решение оптимальным. Кроме того, количество удаленных элементов может быть равно k, что, я думаю, я должен был указать. - person iheartcoding124; 06.11.2020
comment
Да, это сработает. После пропуска текущей записи брать следующую запись необязательно. Повторение допускает несколько пропусков подряд. - person user3386109; 06.11.2020
comment
@ user3386109 как так? Мне кажется, что повторение должно пройти через каждый элемент массива и выполнить проверку как [суммы самого себя с его соседом i+2], так и [его соседа i+1]; после нахождения максимального из этих двух элементов он удаляет элемент с номером i и переходит либо к элементу с номером i+2, либо к элементу с номером i+1 и выполняет ту же проверку. - person iheartcoding124; 06.11.2020
comment
@iheartcoding124 Повторение принимает максимум из: 1) суммы текущего элемента с наилучшим возможным ответом после пропуска одного элемента или 2) наилучшего возможного ответа, начиная со следующего элемента< /б>. Ни в том, ни в другом случае вам не требуется брать следующий доступный элемент. - person user3386109; 06.11.2020
comment
В этом случае я не знаю, приведет ли это на самом деле к специальному решению динамического программирования, которое вычисляет решения один раз; слишком много накладных расходов при рекурсивном использовании MaxDel. - person iheartcoding124; 06.11.2020
comment
@ iheartcoding124 Но результаты MaxDel могут быть записаны и использованы повторно, поэтому простая рекурсия возвращается к динамическому программированию. - person MBo; 06.11.2020
comment
@MBo Да, как только вы упомянули об этом, я пытался сделать мемоизированную версию вашей рекурсии, которая просто запоминает и сохраняет ранее вычисленные результаты в каком-то массиве. Это может избежать необходимости вычислять целое поддерево MaxDel, если мы уже знаем результат этого дерева, и сокращения служебных рекурсивных вызовов. Я думаю, что у него будет та же среда выполнения сложности O(), что и у решения, которое вычисляет все результаты один раз. - person iheartcoding124; 06.11.2020
comment
@ iheartcoding124 Вам не нужно запоминать, чтобы реализовать это решение. Это совершенно не помогает производительности. - person Dai; 07.11.2020