Задача про банкомат и банкноты

@nicenice · Регистрация: 22.11.2011

Студворк — интернет-сервис помощи студентам

Задача, насколько я понимаю, на оптимизацию по двум критериям.
Имеется банкомат с тучей денег. У него банкноты размером 1, 10, 100 единиц (не важно, какие именно).
Нужно, чтобы он отдавал деньги пользователям.

1 критерий оптимизации: количество банкнот должно быть минимальным. тут, по идеи, напрашивается жадный алгоритм, если бы не 2 критерий.

2 критерий оптимизации: количество различных банкнот должно быть максимальным. то есть, если у нас есть возможность отдать банкноты с 1, 10, 100 единицами, их и нужно отдать, не 1, 10 и не 1, 100, если есть возможность.

Пример:
пользователь захотел снять 120 единиц денег. банкомат должен отдать:
1 бумажку - 100 единиц
1 бумажку - 10 единиц
10 бумажек - 1 единицы

3 критерий, о который подразумевается по умолчанию:
пользователь должен получить свои бабки! (если это возможно)

Пока приходит на ум перебор всех возможных вариантов.
Мы их куда-то сохраняем, напр. в ArrayList<int[]>, где размер int[] - число номиналов.
Потом проходимся по всем элементам, узнаем максимальное число номиналов.
Берем элементы с найденным числом номиналов, смотрим у каждого элемента число бумажек с максимальным номиналом (100), если есть совпадения, смотрим на меньший номинал (10) и тд

Этот метод решения мне показался слишком корявым и медленным, как оптимальнее решить задачу?

@Vtulhu · 19.10.2015, 14:30

Надо дать пользователю по одной бумажке каждого номинала. Получится 111 (в нашем примере). А потом как бы "добивать" до нужной суммы. Вот и все. Понятно, что если пользователь просит менее 111 рублей, то условие 2 невыполнимо. Тогда нужно дать ему 10 и 1, т.е. 11 и далее добивать до нужной суммы. Думаю, принцип ясен.

@Shamil1 · 19.10.2015, 14:46

Сообщение от nicenice

У него банкноты размером 1, 10, 100 единиц (не важно, какие именно).

Вообще-то, от номинала банкнот зависит, можно ли набрать требуемую сумму жадным алгоритмом.

Сообщение от nicenice

3 критерий,

Что делать, если не удаётся удовлетворить все 3 критерия. Какие приоритеты?

@nicenice · 19.10.2015, 15:10 **[ТС]**

Vtulhu, Я так же думал, начинал давать юзеру по одной бумажке с самым маленьким номиналом. Потом придумал кучу примеров, когда пользователь не может получить полную сумму.
Например, у нас есть номиналы 2, 5, 9. Пользователь захотел купить чупа-чупс и он хочет снять 10 единиц денег.
Даем ему 2, 5, 2 = 9. На конфетку не хватает! Ок, пошли с конца: 9, ... = 9. А нужно было дать 2 ед. 5 раз.

Или пользователь хочет взять 3 ед. денег, в банкомате номиналы 2, 3. Берем сначала: 2, .. итого не 3.

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

Shamil1, не совсем понял про жадный алгоритм. От номинала зависит, соглашусь, но он для этой задачи вроде не подходит.
Главный приоритет - пользователь должен получить все деньги, которые он запросил, насколько это возможно.
Он должен получить все номиналы валют, насколько это возможно.
Количество полученных бумажек должно быть минимальным, насколько это возможно.
В таком порядке.

@Vtulhu · 19.10.2015, 17:05

В принципе, можно сделать тупой перебор, т.е. получить все возможные варианты количеств банкнот (типа [ 1, 1, 10 ] для суммы 120 рублей), а потом выбрать из них те, где количество нулей минимально. На пайтоне могу написать.

@Shamil1 · 19.10.2015, 17:30

Только проще строить снизу вверх.
Берём сумму "0 рублей; { [0,0,0] }" и находим все суммы, которые можно из неё получить добавлением одной банкноты. Переходим к сумме "1 рублей"... и так далее.

Условный код:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] coins = new int[] {1, 10, 100};
int maxSum = 120;
HashSet<int[]>[] aaa = new HashSet<int[]>[maxSum+1];
aaa[0] = new HashSet<int[]>();
aaa[0].Add(new int[coins.Length]);
for(int i = 0; i < maxSum; i++)
{
    HashSet<int[]> aa = aaa[i];
    for(int j = 0; j < coins.Length; j++)
    {
        int coin = coins[j];
        if(i + coin > maxSum) break;
        if(aaa[i+coin] == null) aaa[i+coin] = new HashSet<int[]>();
        HashSet<int[]> bb = aaa[i+coin];
        bb.AddRange(aa.Select(x => x.WithCoin(j)));
    }
}

@Vtulhu · 19.10.2015, 19:52

Такая мысль тоже была, но если сумма большая, то мы очень долго будем строить.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@nicenice 3 / 3 / 2 Регистрация: 22.11.2011 Сообщений: 168

	Задача про банкомат и банкноты 19.10.2015, 11:18. Показов 15517. Ответов 6 Метки нет (Все метки) Задача, насколько я понимаю, на оптимизацию по двум критериям. Имеется банкомат с тучей денег. У него банкноты размером 1, 10, 100 единиц (не важно, какие именно). Нужно, чтобы он отдавал деньги пользователям. 1 критерий оптимизации: количество банкнот должно быть минимальным. тут, по идеи, напрашивается жадный алгоритм, если бы не 2 критерий. 2 критерий оптимизации: количество различных банкнот должно быть максимальным. то есть, если у нас есть возможность отдать банкноты с 1, 10, 100 единицами, их и нужно отдать, не 1, 10 и не 1, 100, если есть возможность. Пример: пользователь захотел снять 120 единиц денег. банкомат должен отдать: 1 бумажку - 100 единиц 1 бумажку - 10 единиц 10 бумажек - 1 единицы 3 критерий, о который подразумевается по умолчанию: пользователь должен получить свои бабки! (если это возможно) Пока приходит на ум перебор всех возможных вариантов. Мы их куда-то сохраняем, напр. в ArrayList<int[]>, где размер int[] - число номиналов. Потом проходимся по всем элементам, узнаем максимальное число номиналов. Берем элементы с найденным числом номиналов, смотрим у каждого элемента число бумажек с максимальным номиналом (100), если есть совпадения, смотрим на меньший номинал (10) и тд Этот метод решения мне показался слишком корявым и медленным, как оптимальнее решить задачу? 0

@Vtulhu 431 / 385 / 200 Регистрация: 12.08.2011 Сообщений: 1,610
	19.10.2015, 14:30
	Надо дать пользователю по одной бумажке каждого номинала. Получится 111 (в нашем примере). А потом как бы "добивать" до нужной суммы. Вот и все. Понятно, что если пользователь просит менее 111 рублей, то условие 2 невыполнимо. Тогда нужно дать ему 10 и 1, т.е. 11 и далее добивать до нужной суммы. Думаю, принцип ясен. 0

@nicenice 3 / 3 / 2 Регистрация: 22.11.2011 Сообщений: 168
	19.10.2015, 15:10 [ТС]
	Vtulhu, Я так же думал, начинал давать юзеру по одной бумажке с самым маленьким номиналом. Потом придумал кучу примеров, когда пользователь не может получить полную сумму. Например, у нас есть номиналы 2, 5, 9. Пользователь захотел купить чупа-чупс и он хочет снять 10 единиц денег. Даем ему 2, 5, 2 = 9. На конфетку не хватает! Ок, пошли с конца: 9, ... = 9. А нужно было дать 2 ед. 5 раз. Или пользователь хочет взять 3 ед. денег, в банкомате номиналы 2, 3. Берем сначала: 2, .. итого не 3. Мне кажется, если идти таким путем, догадками, то все равно наш алгоритм будет не оптимальным. Нужно что-то математическое, типа задачи с рюкзаком. Shamil1, не совсем понял про жадный алгоритм. От номинала зависит, соглашусь, но он для этой задачи вроде не подходит. Главный приоритет - пользователь должен получить все деньги, которые он запросил, насколько это возможно. Он должен получить все номиналы валют, насколько это возможно. Количество полученных бумажек должно быть минимальным, насколько это возможно. В таком порядке. 0

@Vtulhu 431 / 385 / 200 Регистрация: 12.08.2011 Сообщений: 1,610
	19.10.2015, 17:05
	В принципе, можно сделать тупой перебор, т.е. получить все возможные варианты количеств банкнот (типа [ 1, 1, 10 ] для суммы 120 рублей), а потом выбрать из них те, где количество нулей минимально. На пайтоне могу написать. 0

@Vtulhu 431 / 385 / 200 Регистрация: 12.08.2011 Сообщений: 1,610
	19.10.2015, 19:52
	Такая мысль тоже была, но если сумма большая, то мы очень долго будем строить. 0