Извините, но - генетический алгоритм.
Занимался (в составе коллектива) примерно такой же задачей.
Динамическое программирование позволяло решить оптимально субзадачу примерно в четверть от требовавшегося объема.
Соответственно имелась возможность сверять ошибку генетического алгоритма от оптимального только на уменьшенном объеме - выходило в диапазоне от 0.5% до 2%. При этом по скорости такая субзадача решалась динамическим программированием за 2 часа на 1 сервере (очень много вычислений шло в swap), генетический же алгоритм стабилизировался (с указанной выше ошибкой) примерно через минуту.
