Форум программистов, компьютерный форум CyberForum.ru

Разложить N камней на M Куч - C++

Восстановить пароль Регистрация
 
skiminock
2 / 2 / 0
Регистрация: 11.06.2012
Сообщений: 18
11.12.2013, 14:47     Разложить N камней на M Куч #1
Всем доброго времени суток!
Возникла проблема с решением одной задачи - необходимо разложить N камней на M куч таким образом, чтобы минимизировать вес самой тяжелой кучи. Можете подсказать хотя бы в каком направлении идти?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2013, 14:59     Разложить N камней на M Куч #2
Цитата Сообщение от skiminock Посмотреть сообщение
Можете подсказать хотя бы в каком направлении идти?
жадный алгоритм сразу исключайте. Все зависит от максимальных значений N и M, может быть подойдет простой перебор.
TwilightTwinkle
6 / 6 / 0
Регистрация: 27.11.2013
Сообщений: 26
11.12.2013, 15:10     Разложить N камней на M Куч #3
В смысле одинаково, на сколько это позволяют натуральные числа?
Принцип Дирихле тогда.
C++
1
2
3
4
5
6
7
8
void k(int n, int* m, int c); {
int g=c;
while (n>=0){
m[c]++;
--c;
--n;
if (c<0){
c=g;}}}
Если честно, то я очень долго писал алгоритм с остатками... Затупил чуток.

Добавлено через 54 секунды
Блин, а вес камней то одинаков?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.12.2013, 16:35     Разложить N камней на M Куч #4
(m-1)-мерная динамика. быстрее, насколько я знаю, не решается.

Добавлено через 1 минуту
задача разбиения множества объектов с заданным весом на два равных широко известна, наверное, хорошо гуглится решение с объяснениями.
TwilightTwinkle
6 / 6 / 0
Регистрация: 27.11.2013
Сообщений: 26
11.12.2013, 17:33     Разложить N камней на M Куч #5
/del
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
11.12.2013, 19:43     Разложить N камней на M Куч #6
Цитата Сообщение от skiminock Посмотреть сообщение
Возникла проблема с решением одной задачи - необходимо разложить N камней на M куч таким образом, чтобы минимизировать вес самой тяжелой кучи.
А у камней вес разный?
Если разный, то нужны конкретные ограничения на вес.
Если одинаковый, то все кучи из n/m или n/m-1 камня.
Yandex
Объявления
11.12.2013, 19:43     Разложить N камней на M Куч
Ответ Создать тему
Опции темы

Текущее время: 05:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru