Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной - 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*, но с возможностью сложения строк. Вроде все работает как надо, но есть ли какие-то...

5
valeriikozlov
Эксперт С++
4680 / 2506 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
11.12.2013, 14:59 #2
Цитата Сообщение от skiminock Посмотреть сообщение
Можете подсказать хотя бы в каком направлении идти?
жадный алгоритм сразу исключайте. Все зависит от максимальных значений N и M, может быть подойдет простой перебор.
0
TwilightTwinkle
6 / 6 / 0
Регистрация: 27.11.2013
Сообщений: 26
11.12.2013, 15:10 #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 секунды
Блин, а вес камней то одинаков?
0
salam
173 / 154 / 17
Регистрация: 10.07.2012
Сообщений: 761
11.12.2013, 16:35 #4
(m-1)-мерная динамика. быстрее, насколько я знаю, не решается.

Добавлено через 1 минуту
задача разбиения множества объектов с заданным весом на два равных широко известна, наверное, хорошо гуглится решение с объяснениями.
0
TwilightTwinkle
6 / 6 / 0
Регистрация: 27.11.2013
Сообщений: 26
11.12.2013, 17:33 #5
/del
0
Qwertiy
821 / 629 / 75
Регистрация: 20.08.2013
Сообщений: 2,524
11.12.2013, 19:43 #6
Цитата Сообщение от skiminock Посмотреть сообщение
Возникла проблема с решением одной задачи - необходимо разложить N камней на M куч таким образом, чтобы минимизировать вес самой тяжелой кучи.
А у камней вес разный?
Если разный, то нужны конкретные ограничения на вес.
Если одинаковый, то все кучи из n/m или n/m-1 камня.
0
11.12.2013, 19:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2013, 19:43
Привет! Вот еще темы с ответами:

Написать программу для раздела этих камней на две кучи так, чтобы разность весов этих куч была бы минимальной - Информатика
У нас имеется N камней с весами w1, w2, w3,…, wn. Написать программу, которая распределит эти камни на две кучи так, чтобы разность весов...

Кучи камней разложить на 2 с минимальной разностью - Turbo Pascal
У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, которая распределит камни в две кучи так, что разность весов...

Разложить камни в 2 кучи так, что разность весов двух куч была минимальной - Pascal
Разложить камни в 2 кучи так, что разность весов двух куч была минимальной. Вот мой вариант, однако, неправильный: type list = array...

Дано: X камней, надо разложить эти камни по Y кучкам - Теория вероятностей
Друзья! Собсно, я сам описал все варианты, чтобы вы не думали, что я лодырь. Вот два способа, это две программы на C++, данные задаются в...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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