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

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

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

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

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

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

Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной - C++
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ У вас есть несколько камней известного веса w1, …, wn. Напишите...

Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным - C++
Доброго времени суток! Требуется программу, которая распределит камни в две кучи так, чтобы модуль разности весов этих двух куч был...

Необходимо разбить камни на две кучи таким образом, чтобы веса куч отличались не более чем в 1.5 раза. - C++
Имеется N камней веса А1,А2,...,АN. Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 1.5 раза....

3. Игра Ним с одной кучей камней и с инвертированными правилами - C++
Решите задачу методом динамического программирования : Игра Ним с одной кучей камней и с инвертированными правилами (взявший последний...

Простенькая задачка из Timus Online Judge(1005. Куча камней) - C++
Собственно условие: http://acm.timus.ru/problem.aspx?space=1&num=1005 Моё решение: #include <iostream> using namespace std; void...

Написал свой string. Проверьте код на наличие подводных камней, утечек памяти и других ошибок - C++
Сделал класс, который ведет себя аналогично char*, но с возможностью сложения строк. Вроде все работает как надо, но есть ли какие-то...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 19:43     Разложить N камней на M Куч
Еще ссылки по теме:

Разложить ряд - C++
Требуется разложить ряд..

Разложить в ряд Тейлора - C++
Помогите,срочно пожалуйста!:cry: ex=1+x+x2/2!+x3/3!+...

Как разложить число - C++
например 459 на 4,5,9 эти числа можно например сохранить в массиве int x,mas; cin&gt;&gt;x; //max=здесь числа

Разложить время по компонентам - C++
Возможно ли получить, скажем, текущую секунду системного времени, используя std::chrono, и не опускаясь при этом до уровня time_t?

Разложить на простые множители - C++
разложить целое число на простые множители (код на си)

Разложить функцию в ряд - C++
что то не получается.... и подскажите как мне в одну строку сделать т.е чтобы этого небыло st *= x; а было в одной строке slag = st *...


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

Или воспользуйтесь поиском по форуму:
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