Создание максимальной конфигурации с помощью динамического программирования

У меня была какая-то борьба, пытающаяся решить эту проблему, которую я поставил ниже. У меня есть несколько идей, которые я пробовал. Сначала я решил выбрать все комбинации N кортежей и упорядочить их, но реализация была уродливой, и она должна была замедляться. Я думаю, что существует динамический программный подход к этой проблеме. У меня возникли проблемы с созданием конфигураций. После этого я думаю, что знаю, как решить проблему.

Задача:

Учитывая высоту H (1 <= H < 1 000 000 000), нам нужно найти последовательность высот из N кортежей, которая больше или равна H. Существует несколько условий: Каждый из N кортежей имеет вес, высоту и силу. Сила кортежа указывает максимальное количество общего веса, которое может быть на вершине этого кортежа.

В вопросе задается максимальное значение безопасности стека. Значением безопасности является количество веса, которое может быть добавлено без превышения прочности нижней части кортежа. Если это невозможно, просто распечатайте -1.

INPUT:

Первая строка ввода содержит N и H.

Следующие N строк ввода каждый описывают кортеж, дающий его высоту, веса и силы. Все являются положительными целыми числами не более 1 млрд.

SAMPLE INPUT:

4 10

9 4 1

3 3 5

5 5 10

4 4 5

ВЫХОД ИЗОБРАЖЕНИЯ:

Ответ 1

Хорошо, так как никто другой не разместил решение, я сделаю взломать его.

Учитывая два кортежа, t1 = (h1, w1, s1) и t2 = (h2, w2, s2), мы можем объединить их как либо [t1 over t2] или [t2 over t1]. В каждом случае мы можем рассматривать результат как другой кортеж; например,

t3 = [t1 over t2] = (h1 + h2, w1 + w2, min(s1, s2 - w1))

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

Независимо от порядка композиции, конечная высота и вес кортежа одинаковы; однако результирующая прочность может различаться в зависимости от порядка. Нам интересны кортежи максимальной силы, поэтому мы принимаем максимум двух возможных значений. Учитывая вышеизложенное, определим композицию как

t1 + t2 = (h1 + h2, w1 + w2, max(min(s1, s2 - w1), min(s2, s1 - w2)))

Получаемые кортежи, в свою очередь, могут быть скомбинированы с другими кортежами и т.д.

Нам нужно найти максимальную силу из всех полученных наборов высоты не менее H, так как максимальное значение безопасности, заданное в вопросе, фактически является силой полученного кортежа.

Итак, мы можем установить начальную максимальную силу в -1, начать составлять кортежи и, всякий раз, когда мы находим одну из высоты H или более, обновляем текущую максимальную силу, если сила кортежа больше.

Правило 1: Результирующая сила кортежа не может быть выше, чем любая из двух сильных сторон составных кортежей, поэтому, составляя кортежи, всякий раз, когда мы набираем силу, меньшую или равную максимальному току, мы можем отбросить ее, поскольку кортеж, в котором он будет составлять компонент, может иметь прочность выше текущего максимума.

Правило 1a: Мы можем даже отбросить кортеж, который использовался для обновления текущей максимальной силы, поскольку вопрос не задает нам сам кортеж, просто максимальное значение, и этот кортеж не будет генерировать лучшие максимумы в любой другой комбинации.

Правило 2: Теперь давайте взглянем сверху вниз. Любой стек кортежей n = 2k можно рассматривать как состоящий из двух кортежей, каждый из которых состоит из набора кортежей k; для n = 2k + 1, два стека имеют размер k и k + 1.

Итак, мы строим, чтобы:

список исходных кортежей;
список кортежей, полученный из двух стеков:
список кортежей, состоящий из стеков из трех, с кортежами, состоящими из одного набора из списка [1] и одного кортежа из списка [2] (все комбинации, исключая те, которые используют первичный кортеж дважды);
список кортежей, полученных из стеков из четырех, с кортежами, состоящими из двух кортежей, как из списка [2] (опять же, все комбинации, исключая те, которые используют первичный набор дважды);

и т.д., до N. При создании каждого списка мы обрезаем его согласно правилу 1 выше.

Правило 1b: всякий раз, когда максимальная сила обновляется, все существующие списки должны быть обрезаны кортежами, которые имеют силу, меньшую или равную новому максимуму. Это можно сделать либо немедленно, либо лениво, всякий раз, когда эти кортежи встречаются как часть составления новых кортежей.

Что касается описания алгоритма, я думаю, что это он.

Что касается реализации, я бы сохранил фактические кортежи как std::tuple или struct, с завихрением: для каждого результирующего кортежа вам нужно сохранить список первичных кортежей, из которых он был построен; Я бы использовал для этого std::vector<std::size_t> (содержащий индексы первичных кортежей из первого списка), так как затем вы можете использовать std::find_first_of, чтобы исключить комбинации, которые используют первичный кортеж дважды или даже лучше, если вы сохраните отсортированные списки, std::set_intersection.

Для списков на каждом уровне, std::vector.

Фактический код на С++ - это, конечно же, ваша работа.

Примечание. Алгоритм, описанный здесь, имеет очень плохие худшие характеристики сложности. Наихудший случай для этого решения означает: большой N, большой H, малые кортежи по сравнению с H, малые веса кортежей по сравнению с их сильными сторонами. В таком сценарии ни одна из обрезки, описанная в вышеприведенных правилах, не может наступить до самого позднего времени, и до тех пор, пока это не произойдет, у нас есть комбинаторный взрыв.

Однако для того, что я рассматриваю как более "интересные" случаи, с более равномерными распределениями высот, весов и сильных сторон (аналогично приведенному примеру), я думаю, что это решение будет очень неплохо, даже по сравнению с классическим динамическим программированием решение, которое в этом случае, вероятно, было бы чем-то вроде линии целочисленного решения для ранца с одним перевернутым условием (на самом деле не подумал).

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