Оптимальное решение для создания стопки ящиков
У меня проблема с одним алгоритмом.
Дано n коробок, каждая имеет фиксированный вес и прочность (оба указаны в кг). Прочность коробки говорит нам, какой максимальный вес она может выдержать. Мы должны сформировать самую высокую стопку данных ящиков (каждая из них одинаковой высоты). Вы должны предложить алгоритм, который всегда будет давать оптимальное решение, которое представляет собой самую длинную последовательность из k блоков (k <= n).
Ну, это решение, которое я уже придумал:
- Во-первых, мы сортируем все ящики по их весу (самый тяжелый идет внизу) и формируют их стопку.
- Во-вторых, мы сортируем эту стопку по прочности (самая сильная идет внизу).
- Затем для каждого ящика, начиная снизу, мы пытаемся тянуть его вниз до тех пор, пока это позволяет его сила.
- В конце концов, мы должны выяснить, сколько ящиков должно быть удалено сверху, что вызывает ситуацию, когда некоторые коробки ниже несут гораздо больший вес, чем могли бы.
Кажется, что этот алгоритм работает достаточно хорошо, но я не уверен, всегда ли он дает оптимальное решение - возможно, это не так. Мне было интересно узнать о динамическом решении, похожем на решение проблемы с рюкзаком, но я не уверен, можно ли его решить таким образом. Похоже, что для моей проблемы не существует оптимальной подструктуры.
Заранее благодарю за любую помощь. :)