Дизайн алгоритма: можно ли предоставить решение нескольких задача о ранце?
Я ищу решение псевдокода того, что является эффективно Несколькими Задача о ранце (оператор оптимизации на полпути снижается на страницу). Я думаю, что этой проблемой является NP, Завершенный, таким образом, решение не должно быть оптимальным, скорее если бы это довольно эффективно и легко реализовало, который был бы хорош.
Проблема - это:
- У меня есть много объектов работы с каждым взятием другого (но зафиксированный и известный) количество времени для завершения.
- Я должен разделить эти объекты работы на группы, чтобы иметь самое маленькое количество групп (идеально), с каждой группой объектов работы, берущих не более, чем данный общий порог - говорят 1 час.
Я гибок о пороге - он не должен быть твердо применен, хотя должно быть близким. Моя идея состояла в том, чтобы выделить объекты работы в мусорные ведра, где каждое мусорное ведро представляет 90% порога, 80%, 70% и так далее. Я мог затем соответствовать объектам, которые берут 90% тем, которые берут 10% и так далее.
Какие-либо лучшие идеи?
2 ответа
Насколько мне известно, проблема является NP-полной (Википедия подтверждает ), поэтому, вероятно, нет особого смысла пытаться решить ее точно. Однако любое количество подходов может быть достаточно хорошим для вас: жадные, генетические алгоритмы, имитировать отжиг ... жадность, вероятно, проще всего реализовать:
while (time available in block greater than smallest task duration)
find the longest fitting task
add it
... вы поняли.
Вам понадобится http://www.or.deis.unibo.it/knapsack.html, глава 6.6 "Задача множественных рюкзаков - Приблизительные алгоритмы". В тексте есть псевдокод (стиль Паскаля) и реализации Fortran (да, это старая книга) в виде ZIP-файла.