Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 100000)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.
Тесты
| Сумма | 130 | 999 | 7360 | 3 | 80 | 123450 | 567 | 440 |
| Число купюр | 3 | -1 | 18 | -1 | 3 | 249 | -1 | 4 |
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { int[] Q = { 500, 200, 100, 50, 20, 10 }; int n, q, x; //q - вспомогательная переменная в цикле Scanner sc = new Scanner(System.in); n = sc.nextInt(); x=0; //количество купюр, ему по умолчанию присваивается 0 for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему { q = Q[i]; x += n / q; //считаем, сколько раз входит купюра в сумму n %= q; //сумме присваивается остаток от деления на данную купюр } if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать System.out.format("%d", x); } } |
Алгоритм
В данной задаче очень удобно применить так называемый жадный алгоритм. Он заключается в том, чтобы взять купюру наибольшего достоинства, и найти, сколько раз она входит в данную сумму. То, что мы можем выдать только с помощью этой купюры, отнять от исходной суммы. Затем повторить операцию для оставшегося количества денег и самой большой из купюр меньшего достоинства. Перебрав таким образом все купюры, мы получим наименьшее их количество для получения данной суммы, что от нас, собственно, и требуется.
Такой алгоритм подходит не для всех валютных систем, а только для канонических – таких, в которых каждая купюра большего достоинства превышает меньшую более чем в два раза. В нашем случае это условие соблюдается.
Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения «жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].
Хорошо получилось