#java #algorithm #data-structures #dynamic-programming
#java #алгоритм #структуры данных #динамическое программирование
Вопрос:
Я кодирую для развлечения алгоритм для определения наилучшего порядка построения N строительных объектов. Конечно, каждое здание имеет свои собственные характеристики (такие как стоимость, производство, время строительства, …). Также существует общий порядок построения объектов на основе этих характеристик.
В какой-то момент моего динамического программирования мне нужна адаптированная структура данных, чтобы получить наилучший результат, достигнутый на данный момент, для построения здания k (k <= N). Мне нужна эта структура данных, чтобы каким-то образом «сопоставить» коллекцию здания k (возможно, отсортированную, поскольку построение здания b1, а затем b2 или b2, а затем b1 оставляет меня с теми же N-k зданиями, но, скорее всего, может привести к разным состояниям) с достижением «наилучшего состояния» на данный момент.
Вероятно, я мог бы использовать простой HashMap, но это подразумевает повторение огромного количества коллекций, содержащих одни и те же элементы, не принимая во внимание, что [b1, b2] является вложенной коллекцией [b1, b2, b3, b4], например.
Я надеюсь, что я достаточно ясно выразился по этому вопросу, и я благодарю вас за вашу помощь 🙂
Комментарии:
1. Проблема не на 100% ясна, но, возможно, было бы полезно иметь класс BuildingSet, который может содержать объекты как Building, так и BuildingSet? Тогда у вас мог бы быть BuildingSet x = [b1, b2] и BuildingSet y = [x, b3, b4].
Ответ №1:
Невозможно ответить, не зная структуры ваших решений.
Но, если решение для k можно получить из решения (k-1), вставив здание b в позицию j, тогда вы можете просто использовать hashmap, отображающий целое число i в «дельту» между решением для i и решением для i-1, выраженное парой.
Но необходимость явно иметь дело с дельтами может быть отвратительной, потому что вам нужно выполнить обход, чтобы получить решение. Вы можете решить эту проблему, сообщив delta о ссылочных дельтах (т. Е. передав delta для (k-1) в конструкторе delta для k), а затем предоставив метод getSolution() , который выполняет фактический обход.
Вы можете распространить эту идею на аналогичные структуры решений.
Ответ №2:
Вы можете использовать LinkedHashSet для ключа, а значением является стоимость строительства зданий, содержащихся в наборе, в порядке итерации. Это немного взлом, но в соответствии с хэш-кодом и equals это должно сработать. Если вы предпочитаете быть более явным, используйте хэш-карту set для пары cost и build order.
Ответ №3:
Если ваши решения выглядят как ABC,cost1, ABCD, cost2, создайте связанный список d-> c-> b-> a. Храните решения в виде кортежей cost и ссылки на последний элемент, содержащийся в вашем решении (самый ранний в списке)