Как равномерно рапределить купюры по суммам?

Question

[Андрей Федоров]

Диспозиция такая - есть некоторое количество купюр разного номинала (допустим рублевая линейка 100,200,500,1000,2000,5000). Нужно разделить купюры на N частей. Размеры частей известны. Задача: определить сколько купюр и какого номинала будет в каждой из частей. При этом желательно, чтобы распределение по купюрам было равномерным. Помогите решить математически. Нужно для последующей реализации в коде.

Comments

[Сергей Соколов]

вот вам по 1 купюре каждого номинала:
100, 200, 500, 1000, 2000, 5000

Как вы видите идеальное деление этого богатства на 7 кучек?

[Андрей Федоров]

Сергей Соколов, допустим в некоторых случаях задача не имеет решения. Но отсутствие решений - это то же математическое понятие.

[Сергей Соколов]

Андрей Федоров, уточните условия. Птому, что можно и раздать по 1 купюре и одному не достанется - и это считать решением. А если нет - то какому именно критерию оно не удовлетворило?

[longclaps]

При этом желательно, чтобы распределение по купюрам было равномерным.

@aliencash, желательно - это не математическое понятие.

[Андрей Федоров]

longclaps, объясняю: желательно - это означает, что если решение будет учитывать равномерное распределение - это будет здорово, но решение без учета такого распределения - это тоже будет приемлемым решением.

[Андрей Федоров]

Сергей Соколов, количество купюр каждого номинала - известно заранее. нужно понять сколько купюр нужно положить в каждую часть. Т.е. да, если одна из частей, допустим 25000 рублей, то лучше положить не 4х5000 + 3х1000 + 2х500 + 3х200 + 4х100, а не 5х5000.

[longclaps]

Андрей Федоров, ты какой-то деревянный.
При заданных номиналах купюр элементарный жадный алгоритм даёт точное решение задачи. Я могу это доказать и выписать этот алгоритм.
Но я не стану метать жемчуг перд свиньями делать это в треде, где топикстартер не в состоянии избавиться от своего "желательно".
Глаза завидущие, руки загребущие.

[Сергей Соколов]

Андрей Федоров, т.е. имеете в виду, что идеально, когда число купюр каждой из номинаций одинаково?
Или «весом» решения можно назвать неравномерность числа разных купюр. И этот вес стремиться минимизировать.

[Андрей Федоров]

Сергей Соколов, идеально - это когда купюры каждого конкретного номинала равномерно распределены между частями. Но их количество в частях может быть разным, потому что части могут быть например 10000 и 110000. Если вам удобнее оперировать понятием вес, то да. Но мне все-таки кажется, что эту оптимизацию можно и позже внедрить, а пока даже общего решения никто не предложил.

[Сергей Соколов]

Андрей Федоров, но тут же противоречие. Когда части разные, что будет считаться лучшим вариантом заполнения?

Это всё надо сформулировать, чтобы дать решение, объективно выполняющее поиск "лучшего" варианта.

[Андрей Федоров]

Сергей Соколов, как я вижу ответ - это наборы целочисленных коэффициентов обозначающих количества купюр разных номиналов. На первом шаге определяем эти наборы, на втором - выбираем оптимальный.

[Сергей Соколов]

Андрей Федоров, вот что именно в этой задаче значит "оптимальный", выражаясь строго математическим языком?

[Андрей Федоров]

Сергей Соколов, чем меньше номинал купюры, тем более одинаковым должно быть количество купюр этого номинала в каждой из частей. Подойдет такая формулировка?

Answer 1

[Олег]

Исходные данные
a) массив [{номинал,количество},...,{номинал,количество}]
b) Количество частей

Требуется построить b - массивов .

Проверки существования решения
S = по массиву a_n*a_c ; // сумма к распределению
Sb = S/b ; // Каждому - Должна быть целой , иначе поделить поровну нельзя.
не должно быть купюр номиналом больше Sb ; // рвать и брать сдачу нельзя.

а дальше проще мат моделированием с эвристиками решать, чем
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...