Ответ 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, малые веса кортежей по сравнению с их сильными сторонами. В таком сценарии ни одна из обрезки, описанная в вышеприведенных правилах, не может наступить до самого позднего времени, и до тех пор, пока это не произойдет, у нас есть комбинаторный взрыв.
Однако для того, что я рассматриваю как более "интересные" случаи, с более равномерными распределениями высот, весов и сильных сторон (аналогично приведенному примеру), я думаю, что это решение будет очень неплохо, даже по сравнению с классическим динамическим программированием решение, которое в этом случае, вероятно, было бы чем-то вроде линии целочисленного решения для ранца с одним перевернутым условием (на самом деле не подумал).
Я могу вернуться к этому позже, когда у меня будет время сделать некоторые фактические измерения, просто из любопытства.