«phpClub» — архив тем ("тредов"), посвящённых изучению PHP и веб-технологий.
Аноним 2021/04/23 15:57:14  №2006071 1
Аноны, много лет у нас в задачнике висит задача про Банкомат (есть банкомат, в нем есть ограниченное количество купюр нескольких номиналов, как выдать сумму K?). Но все это время я сам не знал оптимального решения, и предлагал решать ее полным перебором. То есть, берем все возможные комбинации всех банкнот, пока не получим нужную сумму.

Однако, если банкнот много, перебор будет очень долгим. Например, если у нас 1000 банкнот 4 видов, и надо выдать очень большую сумму, то придется перебирать 1000 x 1000 x 1000 x 1000 = 10004 = 1 триллион комбинаций. Даже на современном компьютере это долго. Как же тогда банкоматы справляются с проблемой?

Я даже думал, не поменять ли условия задачи, а то, может быть, я даю нерешаемую задачу людям. А в интернете находятся задачи про банкомат с неограниченным количеством купюр. Однако сегодня, я прочел, что такая задача сводится к задаче о рюкзаке и решаема за более быстрое время за счет динамического программирования.

Кажется, я нашел способ решить задачу быстрее. Например, в примере выше нам потребуется лишь 40002 = 16 миллионов шагов.
Ответы: >>2006096
Аноним 2021/04/23 16:08:53  №2006096 2
>>2006071
Если купюры конкретные, естественных номиналов, то задача конечно простая.

Это когда тебе надо работать с заранее неизвестными купюрами, например в 16, 17, 983 и 3751 рубль (заранее неизвестными), вот тогда уже сложно становится.

Ответы: >>2006110 >>2006112
Аноним 2021/04/23 16:20:53  №2006112 3
>>2006096

Вот пример, где "жадный" алгоритм не работает.

Есть купюры: 5x500, 3x200, 0x100. Надо выдать 600.

Тут "жадный" алгоритм возьмет 1 купюру по 500, останется 100 в остатке, но их он выдать не сможет.
Ответы: >>2006127 >>2006180
Аноним 2021/04/23 16:35:23  №2006127 4
>>2006112
А, понял о чём ты.

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

В любом случае под конкретные купюры задача сильно упрощается, даже с перебором, перебор будет проще.