Задача о распределении по N рюкзакам
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 18.01.23 09:12
Оценка:
Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.

Есть для задачи оптимизации решение лучше перебора с гарантированным нахождением глобального минимума?

Я не смог придумать. Написал в итоге генетический алгоритм, но он даёт локальные минимумы. Пришлось рандомизировать начальные условия и запускать много раз. Так как не требовалось искать минимум, достаточно было найти решение, которое даёт попарные отклонения меньше порога, то задачу я решил.

Спустя время я натолкнулся на скрипт и решил спросить у сообщества есть ли решение. Очевидно что задача обобщается для любого количества рюкзаков.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.