Вот динамическая проблема с программным решением - я не уверен, что это ваше, потому что я не уверен в деталях того, что вы написали, но может быть.
Сортируйте набор чисел и нарисуйте кривую с осью x, дающую смещение числа в отсортированном порядке и ось y, указывающую число. Под кривой будет какая-то площадь.
У вас есть конечное число точек, как правило, меньшее число, чем элементы набора. Вы можете использовать каждую из этих точек, чтобы отметить точку набора, и, следовательно, точку кривой.
Нарисуйте гистограмму под кривой. В каждой отмеченной точке есть линия от этой точки, идущая вправо, поэтому линии полностью находятся под кривой. Каждая такая строка продолжается до тех пор, пока она не достигнет значения x для следующей отмеченной точки, и в этот момент будет линия, идущая к новой отмеченной точке.
Задача состоит в том, чтобы выбрать, какие точки следует маркировать, чтобы максимизировать область под горизонтальными линиями, идущими прямо от отмеченных точек. Это простое динамическое программирование. Если вы можете выбрать до k отмеченных точек, то в каждой точке гистограммы выведите самую большую область, которую вы можете покрыть слева от этой точки, используя отмеченные точки 0, 1, 2, ..k, возможно, включая эту точку. Вы можете решить ответ для каждой точки, обратившись к ответам, которые вы уже разработали, для точек слева от них. Ответ на самую правую точку - ответ на всю проблему.
Чтобы развернуть это: предположим, что вы разрабатываете наилучшие решения для максимальной площади, заканчивающиеся на смещение 10. Для каждого значения j из 0..k рассмотрим возможность использования предыдущего наилучшего решения, заканчивающегося на 0, 1, 2, 3. 9 и поддержание высоты в этой точке, не вводя новую линию. Общая площадь для этого - площадь до этой точки плюс новая площадь, полученная любой высотой, в которой они находились, в этот момент времени до расстояния до этой точки. Также подумайте об этом, но используя дополнительную отмеченную точку в этой точке, поэтому общая площадь является областью лучшего решения с j-1 точками до, например, точка 7 плюс расстояние назад от точки 10 до точки 7 раз выше, достигнутой в точке 7. Рассматривая эти две возможности, вы можете найти лучшее решение в точке 10 с использованием 0,1,2, ... k отмеченных точек.
Я думаю, что эти проблемы связаны с тем, что для каждой отмеченной или отсутствующей точки область, которая она вносит в гистограмму, зависит от высоты линии над ней, которая является высотой наибольшей отмеченной точки, не большей, чем точка мы рассматриваем на данный момент.
Для этого вам понадобится массив элементов kn, которые дают площадь, покрываемую лучшим решением, в каждой точке, используя не более k отмеченных точек.Также будет удобно использовать дополнительный массив такого размера, чтобы записать решение, которое привело к этому лучшему решению, чтобы вы могли отслеживать ответ. Это имеет значение около kn^2, потому что в каждой из n точек вам нужно вычислить значения k и оглянуться на все предыдущие точки, как вы это делаете. Я подозреваю, что вы можете уменьшить это до чего-то вроде O (kn), изменив определение того, что вы храните в каждой точке, чтобы вам никогда не приходилось оглядываться назад, чем предыдущая точка. Если бы вы могли это сделать, вы могли бы экономить на магазине за счет времени, сохраняя только несколько промежуточных точек и решая проблему снова на небольших участках, чтобы отследить назад, но вам нужно будет отчаянно отстать от магазина, чтобы сделать это стоит.
Это определенно похоже на ту же проблему, спасибо! Визуальная интерпретация этого действительно крутая. У меня вопрос о решении. Нужна ли нам таблица элементов nk или просто массив из n элементов? «Правая точка», кажется, предлагает массив. – ManOfNetworks
Кроме того, есть ли у вас какие-либо другие детали для решения? Я по-прежнему изо всех сил пытаюсь думать о повторении отношений для этого. Я не могу понять, как область слева от точки может быть полезна для вычисления области для следующей точки. – ManOfNetworks
Я расширил свой ответ, чтобы попытаться добавить более подробную информацию об этом. – mcdowella