Как равномерно рапределить купюры по суммам? Диспозиция такая - есть некоторое количество купюр разного номинала (допустим рублевая линейка 100,200,500,1000,2000,5000). Нужно разделить купюры на N частей. Размеры частей известны. Задача: определить сколько купюр и какого номинала будет в каждой из частей. При этом желательно, чтобы распределение по купюрам было равномерным. Помогите решить математически. Нужно для последующей реализации в коде.
Как равномерно рапределить купюры по суммам? Диспозиция такая - есть некоторое количество купюр разного номинала (допустим рублевая линейка 100,200,500,1000,2000,5000). Нужно разделить купюры на N частей. Размеры частей известны. Задача: определить сколько купюр и какого номинала будет в каждой из частей. При этом желательно, чтобы распределение по купюрам было равномерным. Помогите решить математически. Нужно для последующей реализации в коде.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для равномерного распределения купюр по суммам можно воспользоваться жадным алгоритмом.
Отсортируйте купюры по номиналу в убывающем порядке.Создайте массив, где будут храниться количество купюр каждого номинала для каждой из N частей.Проходите по отсортированному массиву купюр и для каждой купюры выбирайте такую часть, куда добавление этой купюры не нарушит равномерное распределение.Повторяйте шаг 3 до тех пор, пока все купюры не будут распределены.Пример:
Берем купюру 5000, добавляем в первую часть.Берем купюру 2000, добавляем во вторую часть.Берем купюру 1000, добавляем в первую часть.Берем купюру 500, добавляем во вторую часть.Берем купюру 200, добавляем в третью часть.Берем купюру 100, добавляем в первую часть.Есть купюры: [5000, 2000, 1000, 500, 200, 100]
Нужно разделить на 3 части: [3, 2, 1]
Получаем:
Первая часть: [5000, 1000, 100]
Вторая часть: [2000, 500]
Третья часть: [200]
Таким образом, равномерное распределение купюр по суммам для 3 частей выполнено.