Проблема алгоритма: упаковка стержней в ряд

Question

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

1. У меня есть ряд стержней, которые мне нужно отсортировать.Поскольку это линия, нужно беспокоиться только об одном измерении.
2. Стержни разной длины и разного веса.Там нет корреляции между весом и длиной.Маленький стержень может быть очень тяжелым, в то время как большой стержень может быть очень легким.
3. Удилища должны быть отсортированы по весу.
4. Однако улов real , некоторые стержни могут быть размещены только не более чем на определенных расстояниях от начала линии, независимо от их веса.Однако в любом случае до этого все в порядке.
5. Не дается никаких гарантий, что ограничения будут достаточно разнесены друг от друга, чтобы исключить возможность сдавливания ограниченных стержней.В этом (мы надеемся, редком) случае либо необходимо каким-то образом переставить стержни в пределах их ограничений, чтобы создать необходимое пространство, либо может быть необходимо найти идеальное компромиссное решение (например, нарушение ограничения наименьшего легкого стержня, дляпример.стержни не могут перекрываться.

Мое текущее решение не учитывает последние ситуации, и похоже, что для их решения потребуется сложная работа.

Обратите внимание, что это для клиентского веб-приложения, поэтому было бы полезно сделать решение , применимое к Javascript !

Answer 1

Если это возможно, я бы предложил сформулировать это как смешанную целочисленную программу. Если вы можете закодировать ограничения в этом, вы можете использовать решатель для удовлетворения ограничений. Смотрите эту страницу для получения дополнительной информации об этом типе подхода:

http://en.wikipedia.org/wiki/Linear_programming

Если вы можете как-то связать это с Javascript, то это может оказаться элегантным решением.

Answer 2

Я на 99% уверен, что это может быть приведено как целочисленная задача о ранце с дополнительным ограничением, которое, я думаю, может быть учтено при первом рассмотрении стержней с условием расстояния от начала.

Вот ссылка на объяснение проблемы с рюкзаком: http://www.g12.cs.mu.oz.au/wiki/doku.php?id=simple_knapsack

Answer 3

Сначала я попытался решить эту проблему как проблему сортировки.Но я думаю, что лучше думать об этом как о проблеме оптимизации.Позвольте мне попытаться формализовать проблему.Дано:

• w _i : вес стержня i
• l _i : длина стержня i
• m _i : максимальное расстояние стержня i от начала координат.Если ограничений нет, вы можете установить это значение на сумму (i = 1, n, l _i )

Проблема состоит в том, чтобы найти перестановку a _i, так что функция стоимости:

J = сумма (i = 1, n, w _{a i} * сумма (j = 1, i-1, l _{a j} ))

сведено к минимуму и ограничения:

сумма (j = 1, i-1, l _{a j} ) <= m <sub>i , 1 <= i<li>

Я думаю, что есть некоторые упущенные возможности сделать лучше, потому что мы сдвигаем некоторые стержни к исходной точке, чтобы они все подходили (на шаге 3), и иногда выбираем тяжелые стержни из этих «сжатых» мести поместите их ближе к источнику (в шаге 4).Это освобождает пространство, но мы не сдвигаем оттянутые стержни назад до пределов их ограниченного положения.Это может быть возможно, но мне придется пересмотреть алгоритм, когда мой мозг работает лучше.

Это не очень эффективный алгоритм.У меня есть ощущение, что это можно сделать в O (n ^ 2), но все, что лучше, потребует творческих структур данных.Вы должны быть в состоянии найти самый тяжелый стержень с длиной меньше заданного L быстрее, чем O (n), чтобы добиться большего успеха.

Answer 4

Я не очень хорош в решении алгоритмов. Но вот моя попытка:

Соотнесите это с проблемой Рюкзак

• Вместо стоимости или стоимости из коробки, пусть они будут назначены более высокое значение для тех, кто меньший лимит идти дальше.
• Что-то вроде того, что вы пытаетесь упаковать все ближе к отправная точка, а не в Рюкзак согласно задаче о рюкзаке.
• Что касается будущей даты и модификации Я считаю, что это связано с использованием ограничений, которые аналогичны потребуют изменения в возвращаемое значение или стоимость коробки только.