2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Вопрос про алгоритм
Сообщение22.05.2011, 14:48 


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

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

 Профиль  
                  
 
 Re: Вопрос про алгоритм
Сообщение22.05.2011, 15:25 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос про алгоритм
Сообщение22.05.2011, 15:42 


13/09/09
72
gris в сообщении #448809 писал(а):
То есть фактически надо разложить эти шары как можно более равномерно. По весу-числу, разумеется. Решение — не меньше трети суммы чисел. Вот и набираем в первый мешок не меньше трети, используя самое большое число, потом раскидываем остаток по двум, а дальше динамика.
Это задача распределения камней по трём грузовикам.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group