Вопрос про алгоритм

[Nikita_b]

Задача: У нас есть три мешка и N шаров с натуральными цифрами на них. Нам нужно сложить эти шары в мешки так, чтобы максимальная сумма цифр на шарах в мешке, была минимально возможной.

Попалась такая задача. Как я понял в условии имеется в виду, что максимальная сумма цифр должна быть минимально возможной, при этом шаров в мешке может быть сколько угодно. Есть ли какой-то алгоритм который тут можно использовать? Ограничение по времени выполнения секунда, при условии того, что N там довольно большие, т.е решение должно быть очень простое.
Мои решения элементарно не проходят по времени :(

[gris]

То есть фактически надо разложить эти шары как можно более равномерно. По весу-числу, разумеется. Решение — не меньше трети суммы чисел. Вот и набираем в первый мешок не меньше трети, используя самое большое число, потом раскидываем остаток по двум, а дальше динамика.
Это задача распределения камней по трём грузовикам.

[Nikita_b]

gris в сообщении #448809 писал(а):

То есть фактически надо разложить эти шары как можно более равномерно. По весу-числу, разумеется. Решение — не меньше трети суммы чисел. Вот и набираем в первый мешок не меньше трети, используя самое большое число, потом раскидываем остаток по двум, а дальше динамика.
Это задача распределения камней по трём грузовикам.

Как делал я: Сумму всех чисел делил на три. И собирал из шаров число максимально близкое к этому(В большую сторону само собой). Потом пытался положить оставшиеся шары в другие мешки, так что их сумма была меньше. Если это не получается пытался собрать это же число в первом мешке по другому. Если не получалось пытаемся собрать большее число. И так далее.
Но мне почему-то кажется, что это жутко не оптимально. Должно быть более простое решение.

Про задачу с грузовиками, спасибо. Сейчас поищу.