Частным случаем задачи об упаковке в контейнеры
Уважаемые Эксперты ,
У меня есть реальный жизненный сценарий, где мне нужно решить проблему, связанную со строительством, несколько похожую на проблему упаковки мусорных контейнеров.Ситуация выглядит следующим образом :
У меня есть большое количество кабельных катушек/барабанов (скажем, порядка 20 000 номеров), каждый из которых имеет различную длину (случайные длины от 200 до 3000 метров) кабеля.
Мне приходится резать большое количество кабелей разной длины (которые случайным образом варьируются от 1 метра до 1000 метров).
Я хочу распределить кабели по этим барабанам с двумя целями, а именно: (а) минимизировать потери или минимизировать общий кабель, используемый для всего распределения (б) максимизировать длину ненужных кабелей (например, вместо того, чтобы тратить два 10-метровых кабеля, когда это абсолютно необходимо, я бы попытался потратить один 20-метровый), чтобы увеличить вероятность повторного использования.
Я использовал динамический алгоритм (аналогичный решению задачи о сумме подмножеств), чтобы найти наилучший вариант для конкретной кабельной катушки/барабана и получить довольно хорошее решение.
Однако это не самое оптимальное решение по следующим причинам :
(1)Вначале я не знаю, какой барабан взять первым для распределения. Последовательность, с которой я начинаю распределение, сильно влияет на общую потерю.
(2) когда существует несколько идеальных комбинаций, возможных для нулевых потерь для конкретного барабана, выбор правильной комбинации из них для общей оптимизации является моей задачей.
(3) в конечном итоге я делаю нулевые потери для барабана, где на самом деле я должен держать некоторые преднамеренные потери, чтобы использовать какой-то конкретный кабель, который приведет меня к более чем минимизированным потерям. Это означает, что создание нулевых потерь для барабана не обязательно является лучшим решением (особенно когда длина кабеля составляет от 300 до 800 метров)
Обратитесь за помощью !
С уважением
Что я уже пробовал:
Пробовал с динамическим алгоритмом для задачи суммы подмножеств
Richard MacCutchan
Извините, что мы не делаем вашу домашнюю работу.
Member 13061207
Вероятно, вы не прошли через эту проблему . Это не домашняя работа :). Я понимаю, что это все еще открытая проблема, и многие ppl все еще работают над этим. захотелось свежей идеи.
Richard MacCutchan
Ну, это все равно эффективно домашнее задание. И как Патрис упоминает ниже, есть книги по этому предмету, которые вам нужно изучить. Вы не можете ожидать ответа на такую проблему на форуме быстрых ответов.