Вы входите в магазин, выбираете несколько товаров, затем идете к прилавку, чтобы оплатить счет. Итого некоторое количество (A). Вы достаете в свой кошелек, кошелек или карман и кладете немного денег (P), гдеP > =Aи кассир дает вам сдачу.

Учитывая набор монет и купюр, находящихся в обращении, каковы наиболее вероятные значения дляP?

Некоторые примеры, предполагающие, что доступные счета составляют 5, 10, 20, 50 и 100 долларов, а доступные монеты 5с, 10с и 25с:

A = $ 151,24
P[1] = 160 (8x20) или (100 + 3x20)
P[2] = 155 долларов США (100 долларов США + 50 долларов США + 5 долларов США)

A = 22,65 $
P[1] = 25 долларов США (20 долларов США + 5 долларов США)
P[2] = 30 долларов США (20 долларов США + 10 долларов США)
P[3] = 40 долларов (20 долларов + 20 долларов)

A = 0,95 $
P[1] = 1 доллар (4 х 25 центов)
P[2] = 5 долларов

Многие из этих чисел кажутся интуитивно понятными, но у меня есть ощущение, что алгоритм сложно определить.