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

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

Постановка задачи:

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

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

ВХОД:

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

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

ОБРАЗЕЦ ВХОДА:

4 10

9 4 1

3 3 5

5 5 10

4 4 5

ОБРАЗЕЦ ВЫХОДА:

2

11

Решение

Ну, так как никто не опубликовал решение, я воспользуюсь им.

Учитывая два кортежа, 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: Сила результирующего кортежа не может быть выше, чем любая из двух сильных сторон кортежей компонентов, поэтому при составлении кортежей всякий раз, когда мы находим один из сил, меньших или равных текущему максимуму, мы можем его отбросить, так как нет кортежа, в котором он будет компонент может иметь силу выше, чем текущий макс.

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

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

Итак, строим по порядку:

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

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

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

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

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

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

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


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

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

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

9

Другие решения