| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Размещение монеток |
| Автор: nIkTo 22.11.2010, 21:14 |
| У Вани 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) Если номинал монеты выше чем сумма максимальной кучки, то необходимо положить её в эту кучку и пересчитать % остальных кучек с учётом увеличения текущей кучки. Подскажите какой алгоритм посмотреть для решения этой задачи. |
| Автор: sandland 27.11.2010, 14:42 |
| мне кажется, это задача подходит под задачу о распределении ресурсов в линейном программировании. Ели посмотреть на нее, как на доставку грузов из пункта А в Б с определенной стоимостью доставки. Попробуйте покопать в этом направлении, построить граф. И я бы начал решать поэтапно. Возможно сначала стоит попробовать решить задачу без п.1. Первой что приходит в голову - распределять монеты, начиная с самого высокого номинала в кучки слева на право. И на каждом этапе смотреть, нет ли переполнения процентов, если есть - на этапе еще и перераспределяем %. Далее переходим на более низкий номинал и т.п.. Естественно, что на каждом шаге нужна проверка, не заполнена ли кучка окончательно. |