Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
Есть для задачи оптимизации решение лучше перебора с гарантированным нахождением глобального минимума?
Я не смог придумать. Написал в итоге генетический алгоритм, но он даёт локальные минимумы. Пришлось рандомизировать начальные условия и запускать много раз. Так как не требовалось искать минимум, достаточно было найти решение, которое даёт попарные отклонения меньше порога, то задачу я решил.
Спустя время я натолкнулся на скрипт и решил спросить у сообщества есть ли решение. Очевидно что задача обобщается для любого количества рюкзаков.
G>Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
G>Есть для задачи оптимизации решение лучше перебора с гарантированным нахождением глобального минимума?
Выглядит как задача целочисленного программирования, только целевая функция не целочисленная.
Ещё задачу усложняет то, что у тебя 2 критерия оптимизации: по весу и объему. Придется выбирать что-то одно, или приводить к одному критерию через веса.
Эвристика:
1. сортируем вещи по убыванию "критерия" (вес или объем)
2. выбираем наименее заполненый рюкзак
3. кладем очередную вещь в этот рюкзак.
4. иди в п.4 пока есть вещи
G>Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
Здравствуйте, ilnar, Вы писали:
I>Ещё задачу усложняет то, что у тебя 2 критерия оптимизации: по весу и объему. Придется выбирать что-то одно, или приводить к одному критерию через веса.
Увы важно именно оба.
Здравствуйте, cppguard, Вы писали:
C>Здравствуйте, gandjustas, Вы писали:
G>>Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
C>https://en.wikipedia.org/wiki/Knapsack_problem#Solving
Как решать задачу с одним рюкзаком я в курсе. Как сделать с множеством рюкзаков?
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, cppguard, Вы писали:
C>>Здравствуйте, gandjustas, Вы писали:
G>>>Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
C>>https://en.wikipedia.org/wiki/Knapsack_problem#Solving G>Как решать задачу с одним рюкзаком я в курсе. Как сделать с множеством рюкзаков?
Видимо, так же только каждый раз будет не 2 варианта, а 2 ^ N вариантов
G>Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
А точки равновесия по Нэшу не смотрели? Может ведь и получиться.
Konstantin.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, ilnar, Вы писали:
I>>Ещё задачу усложняет то, что у тебя 2 критерия оптимизации: по весу и объему. Придется выбирать что-то одно, или приводить к одному критерию через веса. G>Увы важно именно оба.
ну не упрямся!
придумай формулу хорошести, типа X=F(вес,объем) и по ней оптимизируй.
G>Есть около 50 "вещей". У каждой вещи есть "объем" (целое число больше 0, максимум около 15) и "вес" (вещественное число, больше нуля, максимум около 30). Все вещи надо распихать по 4 рюкзакам максимально равномерно (минимальная сумма квадратов попарных разностей объема и веса, можно не нормировать), оставлять ничего нельзя.
G>Есть для задачи оптимизации решение лучше перебора с гарантированным нахождением глобального минимума?
G> Я не смог придумать. Написал в итоге генетический алгоритм, но он даёт локальные минимумы. Пришлось рандомизировать начальные условия и запускать много раз. Так как не требовалось искать минимум, достаточно было найти решение, которое даёт попарные отклонения меньше порога, то задачу я решил.
G>Спустя время я натолкнулся на скрипт и решил спросить у сообщества есть ли решение. Очевидно что задача обобщается для любого количества рюкзаков.
отсортировал предметы по нему, и использовал жадный алгоритм для раскидывания по рюкзакам, наичная с самых тяжелых, по эжтму потиенциалу.
Было бы интересно посмотреть на несколько типичных наборов входных данных...
Может оказаться, что есть какая-то очень относительно простая эмпирика для характерных входных данных...
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, ilnar, Вы писали:
I>>Ещё задачу усложняет то, что у тебя 2 критерия оптимизации: по весу и объему. Придется выбирать что-то одно, или приводить к одному критерию через веса. G>Увы важно именно оба.
Вы наверное думаете, что оба критерия легко совместить.
Но на практике могут быть такие входные дынные, где два критерия диаметрально противоположны
Вам придется выбрать функцию, которая их комбинирует
.
