Структура данных для «сопоставления» коллекций с состояниями в алгоритме динамического программирования

Question

Я ради забавы кодирую алгоритм для определения наилучшего порядка построения объектов N Building.Конечно, у каждого Здания есть свои особенности (такие как стоимость, производство, время строительства, ...).Также существует полное упорядочение объектов Building на основе этих характеристик.

В какой-то момент в моем динамическом программировании мне понадобилась адаптированная структура данных для получения наилучшего результата, достигнутого на данный момент, для построения k (k <= N) Строительство.Мне нужна эта структура данных, чтобы каким-то образом «отобразить» коллекцию k Building (возможно, отсортированную, так как построение Building b1, а затем b2 или b2, а затем b1 оставляет меня с теми же зданиями Nk, но, скорее всего, может привести к различным состояниям) к«наилучшее состояние» пока что достигнуто. </p>

Я мог бы, вероятно, использовать простой HashMap, но это подразумевает повторение огромного количества раз коллекций, содержащих одинаковые элементы, не принимая во внимание, что [b1, b2] является подэлементомнапример, коллекция [b1, b2, b3, b4].

Надеюсь, я достаточно ясно высказался по этому вопросу и благодарю вас за вашу помощь:)

Answer 1

Вы можете использовать LinkedHashSet для ключа, а значение - это стоимость построения Зданий, содержащихся в наборе в его итерационном порядке.Это что-то вроде хака, но в соответствии с hashCode и равными он должен работать.Если вы предпочитаете быть более явным, используйте хэш-карту, состоящую из пары стоимости и порядка сборки.

Answer 2

Если ваши решения выглядят как ABC, cost1, ABCD, cost2, создайте связанный список d-> c-> b-> a. Храните решения в виде наборов затрат и ссылки на последний элемент, содержащийся в вашем решении (самый ранний в списке)

Answer 3

Невозможно ответить, не зная структуры ваших решений.

Но, если решение для k можно получить из решения (k-1), вставив здание b в позицию j, то вы можете просто получить целое число отображения хэш-карты i в «дельту» между решением для i и решение для i-1, выраженное парой.

Но иметь дело с явными дельтами может быть отвратительно, потому что вам нужно выполнить обход, чтобы получить решение. Вы можете решить эту проблему, сообщив дельте ссылочные дельты (то есть передав дельту для (k-1) в конструкторе дельты для k), а затем выставив метод getSolution(), который выполняет фактический обход.

Вы можете распространить эту идею на подобные структуры решений.