Разложить число.

[KumoKairo]

Я думаю там можно обойтись простым алгоритмом с использованием наибольшего делителя из заданных.
То есть берем число, берем массив номиналов. Находим наибольший делитель из заданных номиналов, чтобы при целочисленном делении результат не был равен нулю (если делимое больше делителя, то после целочисленного деления получится ноль). Считаем это первым номиналом, запоминаем, увеличиваем счетчик найденных номиналов. Вычитаем из числа номинал, получаем новое число, которому таким же образом находим максимальный из возможных номинал. В итоге у нас получится какое-то количество (M) номиналов, которое будет или не будет равно желаемому количеству (N). Если M != N, то произвольно (или любым другим способом) берем один из имеющихся (найденных) номиналов, которые можно разложить с помощью других потенциальных номиналов, и раскладываем. Снова проверяем M != N, при необходимости повторяем

То есть в случае с вашим примером с 2.53 по этому алгоритму найдется список номиналов [1, 1, 0.5, 0.01, 0.01, 0.01], а потом номинал 1 разложится на два номинала 0.5
Если нужно, могу накатать саму программу)

[Zebestov]

KumoKairo, а накатай. Ну и на работу вместо pivnoibaron выходи!

[alatar]

Мне вот интересно, вот выложит тут кто-то алгоритм (в принципе задача о поиске пути в графе), получит pivnoibaron работу (если на интервью не завалится), а дальше что? Там же работать придется и не всегда можно будет вовремя получить решение задачи на форуме.

[Zebestov]

Я и alatar (почти одновременно) лишь высказали свое отношение к уровню современных "специалистов" и их подходом к своему профессиональному развитию в контексте этой темы. Обсуждать "критерии составления тестовых заданий" предлагаю где-нибудь во Флейме.

[GBee]

А задача прикольная, я че то в лоб ничего придумать не могу. Все упирается в кол-во монеток.

[-De-]

Не можете придумать хорошо - решите прямым перебором.

[Zebestov]

Ну как бы алгоритм делится на два: сначала мы само собой находим минимальную комбинацию, потом "растягиваем" ее до указанного числа путем дробления.

[alatar]

В принципе это один алгоритм. Дробление это тоже поиск минимальной комбинации, только в качестве цели берется число из уже полученной последовательности, пока не будет достигнута необходимая длина.

[iflamberg]

Да, ладно разлагольствовать. Автор темы уже давным-давно взял решение из №6. Которое, кстати не сработает на сложных случаях, типа:
Номиналы: [1.1, 1, 0.2]
Нарезать 2.3

Но, такой случай не реалистичен, конечно.

[-De-]

А как растягиваем? Например если монеты 10, 11, 110, число 110, из 11 монет собрать.