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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
skiminock
2 / 2 / 0
Регистрация: 11.06.2012
Сообщений: 18
#1

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

11.12.2013, 14:47. Просмотров 569. Ответов 5
Метки нет (Все метки)

Всем доброго времени суток!
Возникла проблема с решением одной задачи - необходимо разложить N камней на M куч таким образом, чтобы минимизировать вес самой тяжелой кучи. Можете подсказать хотя бы в каком направлении идти?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2013, 14:47     Разложить N камней на M Куч
Посмотрите здесь:

Необходимо разбить камни на две кучи таким образом, чтобы веса куч отличались не более чем в 1.5 раза. C++
C++ 3. Игра Ним с одной кучей камней и с инвертированными правилами
Разложить на простые множители C++
Простенькая задачка из Timus Online Judge(1005. Куча камней) C++
Разложить в ряд Тейлора C++
Разложить функцию в ряд C++
Разложить время по компонентам C++
Как разложить число C++
Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным C++
C++ Написал свой string. Проверьте код на наличие подводных камней, утечек памяти и других ошибок
Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной C++
C++ Разложить ряд

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4667 / 2493 / 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
818 / 626 / 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 Куч
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru