У Винклера проблема со сбором пиццы:
- Круглый
n
кусочек пиццы из кусочков, где кусочекi
имеет площадь,S_i
т.е. площадь отличается для каждого кусочка пирога. - Пожиратели Алиса и Боб по очереди выбирают кусочки, но было бы глупо создавать несколько пробелов в круговой диаграмме (считайте, что это не разрешено).
- Таким образом, каждый едок ограничен взятием одного из двух кусочков, прилегающих к открытой области. Алиса идет первой, и оба едока ищут как можно больше пирога.
Как алгоритм динамического программирования определяет, сколько пирога ест Алиса, если Алиса и Боб играют идеально, чтобы максимизировать потребление пиццы?
Мое понимание:
В общей проблеме DP мы продолжаем поиск подзадач, которые можно визуализировать с помощью дерева рекурсии или, более точно, с помощью DAG. Здесь я не нахожу никакой возможности найти подзадачи здесь.
Здесь, для данного набора S_i, нам нужно максимизировать площадь кусочков, которые съела Алиса. Это будет зависеть от выбора перестановки ломтиков пиццы из (n-1) перестановок. Выбор максимальной области среза из двух вариантов, доступных через каждые n \ 2 оборота, которые получает Алиса, даст нам общую площадь среза для перестановки. Нам нужно найти площадь среза для всех таких перестановок. И тогда максимум из них.
Может кто-нибудь помочь мне, как идти вперед?
источник
pizzaAmount
зависит только от того, каковы индексы начала и конца оставшихся кусочков, а не от последовательности того, какие кусочки пиццы вы и ваш друг уже съели, чтобы вы могли сохранить результат в матрица, чтобы избежать пересчета. Порядок алгоритма поэтому O (n ** 2).Для части пиццы определите
F(i,j)
как максимум, сколько человек может съесть первым кусочком. Кусочками части пиццы(i,j)
являются:Определите
R(i,j)
(сколько осталось для второго человека) какsum(S_x, x in slices(i,j)) - F(i,j)
.С:
Максимум, что может съесть Алиса, рассчитывается по формуле:
источник