Что такое алгоритм для разделения группы элементов на 3 отдельные группы?

Question

У меня есть эта проблема в моем учебнике: учитывая группу из n элементов, каждый из которых имеет отдельное значение V (i), каков наилучший способ разделить элементы на 3 группы, чтобы свести к минимуму группу с наибольшим значением?Дайте значение этой самой большой группе.

Я знаю, как сделать вариант этой задачи с двумя стопками: для этого нужно просто запустить алгоритм рюкзака в обратном направлении.Тем не менее, я довольно озадачен тем, как решить эту проблему.Кто-нибудь может дать мне какие-нибудь указатели?

Ответ: Почти то же самое, что и рюкзак 0-1, хотя 2D

Answer 1

Пусть f [i] [j] [k] обозначает, возможно ли иметь значение j в первом наборе и значение k во втором наборе, с первые элементы .

Итак, у нас есть f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]].

и изначально у нас есть f[0][0][0] = True.

для каждого f[i][j][k] = True, обновление вашего ответа зависит от того, как вы определите довольно .

Answer 2

Сложная домашняя задача. По сути, это версия оптимизации с 3 разделами.

http://en.wikipedia.org/wiki/3-partition_problem

Он тесно связан с упаковкой, разделением и суммой подмножества (и, как вы заметили, ранцем). Тем не менее, он оказывается сильно NP-Complete, что делает его сложнее, чем его кузены. В любом случае, я предлагаю вам начать с рассмотрения динамических программных решений связанных проблем (я бы начал с раздела, но нашел бы объяснение решения DP, не относящееся к Википедии).

Обновление: извиняюсь. Я ввел вас в заблуждение. Задача с 3 разделами разбивает входные данные на наборы из 3, а не 3 наборов. Остальная часть того, что я сказал, все еще применима, но с новой надеждой, что ваш вариант не является полностью np-полным.

Answer 3

Я не знаю насчет математики «Лучшее», но одним очевидным подходом было бы создать популяцию групп, изначально имеющих по одному предмету в каждой группе. Затем, если у вас больше групп, чем нужно количество конечных групп, извлеките две группы с наименьшими значениями и объедините их в новую группу, которую вы добавите обратно в коллекцию. Это похоже на то, как строятся деревья сжатия Хаффмана.

Пример:

1 3 7 9 10
becomes
4(1+3) 7 9 10
becomes
9 10 11(1+3+7)