Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Размещение монеток 
:(
    Опции темы
nIkTo
Дата 22.11.2010, 21:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 218
Регистрация: 5.7.2007

Репутация: нет
Всего: нет



У Вани 2000 монет различного номинала, к примеру:
15625 - 5 шт.;
3125 - 25 шт.;
625 - 70 шт.;
125 - 150 шт.;
25 - 300 шт.;
5 - 450 шт.;
1 - 1000 шт.;
Общая сумма денег : 229500
Ване необходимо разложить все монетки на 10 различных кучек, стоимости которых будут примерно равны: 20%,15%,10%,9%,9%,9%,7%,7%,7%,7% от общей суммы денег (229500).
При раскладывании руководствоваться следующими приоритетами:
1) Количество монеток (одного номинала) в равных кучках должны быть примерно одинаковыми.
2) Если номинал монеты выше чем сумма максимальной кучки, то необходимо положить её в эту кучку и пересчитать % остальных кучек с учётом увеличения текущей кучки.

Подскажите какой алгоритм посмотреть для решения этой задачи.
PM   Вверх
sandland
Дата 27.11.2010, 14:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 78
Регистрация: 28.4.2007

Репутация: нет
Всего: 1



мне кажется, это задача подходит под задачу о распределении ресурсов в линейном программировании. Ели посмотреть на нее, как на доставку грузов из пункта А в Б с определенной стоимостью доставки. 
Попробуйте покопать в этом направлении, построить граф. 

И я бы начал решать поэтапно. Возможно сначала стоит попробовать решить  задачу без п.1.

Первой что приходит в голову - распределять монеты, начиная с самого высокого номинала в кучки слева на право. И на каждом этапе смотреть, нет ли переполнения процентов, если есть - на этапе еще и перераспределяем %.
Далее переходим на более низкий номинал и т.п.. 
Естественно, что на каждом шаге нужна проверка, не заполнена ли кучка окончательно.

PM MAIL WWW ICQ Jabber   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0541 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.