Возможно кто-то уже имел дело с такой задачей или знает, где есть готовый алгоритм.
Задача такова:
Есть набор товаров с разным весом, например 5 штук продукта "A" с весом по 3кг и 3 штуки продукта "Б" с весом по 2кг.
Есть сумка с максимальным весом N (допустим, 7кг).
Надо распределить все продукты как можно более поровну по сумкам.
У меня есть мысли, как можно решить, если знаешь количество сумок.
В общем решение этой я встречал и в сети, например, аналогичная задачи про пирожки.


Мне надо решить эту задачу, когда неизвестно количество сумок, т.е я могу взять столько сумок, сколько хочу, главное чтобы было как можно более поровну.
Пример:
Сумка = максимум 15кг.
Продукты: 10шт по 7 кг и 3шт про 3кг.

Можно разместить 7кг-продукты в 5 сумок по 2 в каждую сумку.
Выйдет в каждой сумке по 14.
Оставшиеся 3кг-продукты в одну сумку, выйдет 9кг.
Разница между весом в сумках будет 14-9=5кг. Не очень равномерно.

А можно каждый 7кг продукт в свою сумку, а оставшиеся 3кг продукты еще в 1 сумку.
Выйдет 11 сумок, десять по 7кг и одна с 9кг . Разница будет всего 2кг = более-менее равномерно.

Любые советы будут полезными, и заранее спасибо.

я знаю задачу о рюкзаке, вот только связь с моей там очень отдаленная

Да не надо мне готовый код, вы что =) просто на словах подкиньте идею, вот как ув. White Owl, только я не совсем понял, что Вы имеете в виду,
авторто просто делай цикл: от веса максимального предмета и до максимального объема.
В этом цикле набиваешь классические рюкзаки.
по каком принципу набивать?

У меня пока что идея брать число N=1 - кол-во сумок.
И дальше набивать по принципу
1. Для каждого продукта от самых тяжелых к самым легким
2. Найти самую пустую сумку
3. Положить туда продукт
4. Если не помещается N+=1 и по новой
5. Посчитать разницу Diff между самой тяжелой и самой легкой сумкой и запомнить (PreviousDiff = Diff).
6. Если Diff = 0 или Diff не меньше PreviousDiff то конец.

Но это как-то уже слишком не оптимально, т.е. перебирать все возможные количества сумок чревато большим временем выполнения. Правильнее даже сразу брать N = FLOOR (Суммарный вес предметов / максимальный вес сумки), т.е. число сумок, меньше которого быть не может. Но все равно.
Кроме того, алгоритм обладает недостатками.
Если у меня 50 предметов по 2кг и 100 предметов по 1кг и сумка на 100кг, я могу поделить на 2 сумки не разбивая продукты в рагу, а это как раз важная часть моей задачи, т.е. желательно соблюдать однородность состава. А вышеописанный алгоритм будет сначала 50 раз тыкать по 1му продукту каждый раз в новую сумку.

Даже немного не так,
Шаг 6. Если Diff = 0, то конец (оптимальный вариант с количеством сумок N)
Шаг 7. Если Diff не меньше Previous Diff, то конец (оптимальный вариант с количеством сумок N-1)
Шаг 8. N=+1 и все по новой.

авторТ.е. математически что конкретно следует минимизировать?
А что тут непонятного? Чтобы разница веса между максимально и минимально набитыми сумками была минимальной из возможных.
В простом виде это единственное требование.
Насчет однородности это скорее пожелание (на данном этапе), чем требование.
авторА то уже все изнывают, готовясь решать
смешно =)

авторПри достаточно большом числе сумок, метод случайной раскладки даст неплохое приближение к оптимальной. А если если ввести комплексный критерий, с учетом времени решения, то случайная раскладка просто не имеет конкурентов. Но, конечно, при достаточно большом числе сумок.
А можно чуть по-конкретнее? Основная проблема, как я уже говорил, это неизвестность заранее количества сумок.
Брать рандомное количество сумок из диапазона (меньше быть не может, больше не имеет смысла) ? И что потом? случайным образом раскидывать продукты? а смысл, если зная количество сумок, я могу применить более оптимальный алгоритм?

Вообще можно что-то поконкретнее, а то вижу либо вопросы, либо абстрактные закидоны, аля "это обычная задача на....", "тут неплохо бы применить xxx"

склоняюсь к решению, подсказанному White_Owl.
ps: это так задумано, что нельзя редажить посты?=)