Задачата за монетите
Накратко: Задачата за монетите търси най-малко монети за дадена сума; таблицата на динамичното програмиране я решава за O(сума × монети), казва кои са монетите и брои начините.
Проблем
Рестото на автомата
Автоматът на паркинга връща ресто. Има по една туба за всяка от осемте евро монети: 1, 2, 5, 10, 20 и 50 цента, 1 € и 2 €. Колкото по-малко монети връща, толкова по-рядко някой трябва да зарежда тубите. Затова рестото трябва да е с най-малко монети.
Програмистът не иска да гадае и пише рекурсия, която пробва всичко: за всяка монета, която се събира в рестото, „тази монета плюс най-доброто за остатъка“, и взима най-малкото. Сумите са в центове, а броячът брои пробваните монети:
tries = 0
def fewest(coins, amount): global tries if amount == 0: return 0 best = amount + 1 for coin in coins: if coin > amount: break tries += 1 count = fewest(coins, amount - coin) + 1 best = min(best, count) return best
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [10, 20, 30]: tries = 0 count = fewest(coins, amount) print(f"{amount} цента: {count} монети, {tries} опита")10 цента: 1 монети, 309 опита20 цента: 1 монети, 66281 опита30 цента: 2 монети, 14158888 опитаОтговорите са верни. Но за 30 цента рекурсията пробва 14 158 888 монети, а за 40 цента 3 024 560 419. Рестото от 63 цента иска 689 951 222 249 236 опита: при милиард в секунда това са осем дни, докато шофьорът чака на бариерата.
Идеята
Таблицата
Рекурсията пита отново и отново едно и също: най-доброто за 13 цента, за 8 цента, за 3 цента. Това са припокриващите се подзадачи от предишния урок. Само че тук от всяка сума излизат до осем клона, по един за всяка монета, и дървото расте още по-бързо.
Затова строим таблица отдолу нагоре. Една таблица за динамично програмиране се описва с четири неща:
- Какво значи клетката. best[a] е най-малкият брой монети за точно a цента.
- Откъде идва. Последната монета е някоя от тези, които се събират. Значи best[a] е 1 + best[a − монета] за най-добрата монета.
- В какъв ред се пълни. a − монета е по-малко от a. Отляво надясно всичко, което клетката чете, вече е готово.
- Къде е отговорът. В последната клетка, best[рестото]. Началото е best[0] = 0: нула цента не искат монети.
Това е DP таблица: клетка за всяка подзадача, пълнена в ред, в който всяка клетка заварва готови тези, от които зависи. Като в предишния урок, само че изборът в клетката е между повече възможности.
Виж го
Клетка по клетка
Таблицата за 9 цента. Гледай стрелките: всяка идва от клетката a − монета, а клетката a пази най-малкото, което е видяла:
def change(coins, amount): best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return usedСтъпка по стъпка, с думи
- change(coins, 9): best[a] е най-малкият брой монети за a цента, last[a] е монетата, с която се стига дотам. best[0] = 0: нула цента не искат монети.
- За всяко a отляво надясно пробвай всяка монета до a: една монета плюс най-доброто за остатъка, best[a − монета] + 1. Стрелката идва от тази клетка.
- a = 5: монетата 1 дава best[4] + 1 = 3, монетата 2 дава best[3] + 1 = 3, монетата 5 дава best[0] + 1 = 1. Клетката пази най-малкото, а last помни монетата.
- Монетите са подредени от малката към голямата, а 10 вече е повече от 9: цикълът спира там. Всяка клетка чете само клетки вляво от нея, а те вече са окончателни.
- Назад по last: 9 → 7 → 5 → 0. Монетите са 2 + 2 + 5. 22 опита за 9 цента, всяка клетка решена веднъж.
coins = [1, 2, 5, 10, 20, 50, 100, 200]print(change(coins, 9))[2, 2, 5]amount + 1 е „още нищо“: повече монети от центовете няма как да трябват, защото и с еднецентови стигат точно amount. Затова първата пробвана монета винаги е по-добра.Идеята
Кои монети
Броят не стига: автоматът трябва да знае и кои монети да пусне. Затова до best[a] таблицата пази и last[a], монетата, с която се стига до най-доброто за a. Накрая тръгваш от рестото: пускаш last[a], вадиш я, и повтаряш, докато стигнеш 0.
tries = 0
def change(coins, amount): global tries best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break tries += 1 count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return used
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [63, 480]: tries = 0 used = change(coins, amount) text = " + ".join(map(str, used)) print(f"{amount} цента: {text}, {tries} опита")63 цента: 1 + 2 + 10 + 50, 296 опита480 цента: 10 + 20 + 50 + 200 + 200, 3460 опита296 опита за 63 цента вместо 689 951 222 249 236. Таблицата има по една клетка на цент, а всяка клетка пробва най-много осемте монети. Работата е O(n · k): n цента по k вида монети. С k = 8 това е линейно в рестото.
Пробвай
Попълни
Една монета плюс най-доброто за остатъка. Коя клетка чете опитът?
def change(coins, amount):
best = [0] * (amount + 1)
last = [0] * (amount + 1)
for a in range(1, amount + 1):
best[a] = amount + 1
for coin in coins:
if coin > a:
break
count = best[] + 1
if count < best[a]:
best[a] = count
last[a] = coin
used = []
a = amount
while a > 0:
used.append(last[a])
a -= last[a]
return usedОстатъкът след монетата е a - coin цента, а най-доброто за него вече е в таблицата, защото е вляво. Една монета повече е + 1.
Идеята
А защо не най-голямата монета първо?
Касиерът прави друго: дава най-голямата монета, която се събира, и повтаря. За 63 цента това е 50, 10, 2, 1: пак четири монети. С евро монетите това правило винаги дава най-малкия брой. Монетите са подбрани така.
Но правилото зависи от системата монети. При други монети, или когато в автомата свърши някоя туба, „най-голямата първо“ може да даде повече монети от нужното. Кога то работи и кога лъже, е урокът „Кога алчният алгоритъм греши“. Таблицата не разчита на това: тя пробва всяка монета за всяка сума и намира най-малкото при всякакви монети.
Идеята
По колко начина
Друга задача със същата таблица. Банкоматът изплаща суми с банкноти от 5, 10, 20 и 50 €. Тестерите искат да проверят всеки възможен пакет за 100 € и питат: колко са?
Сега клетката е count[a]: по колко начина се събират точно a евро. count[0] = 1, празният пакет. Външният цикъл е по банкнотите, вътрешният по сумите:
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]notes = [5, 10, 20, 50]print(ways(notes, 100), "начина")49 начинаРедът на циклите е важен. Когато петиците са изцяло преди десетиците, всеки пакет се сглобява в един ред: първо петиците, после десетиците. Затова 5 + 10 и 10 + 5 са един и същ пакет и се броят веднъж. И тук никой не търси минимум: клетката събира броя на начините от клетките вляво.
Пробвай
Предвиди изхода
Колко пакета има за 20 € с банкноти от 5, 10 и 20?
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]
notes = [5, 10, 20]print(ways(notes, 20), "начина")Една двадесетачка; две десетачки; една десетачка и две петачки; четири петачки. Четири пакета. 6 е броят на поредиците: 10 + 5 + 5, 5 + 10 + 5 и 5 + 5 + 10 са три от тях, но пакетът е един.
Пробвай
Намери грешката
Колега е написал същото броене, но за 100 € излиза много повече:
notes = [5, 10, 20, 50]print(ways(notes, 100), "начина")48007 начинаНа кой ред е грешката?
Избери реда с грешката.
Външният цикъл е по сумите, а вътрешният по банкнотите. Така за всяка сума се пробва всяка банкнота като последна, независимо от предишните, и всяка подредба на един пакет се брои отделно: 5 + 10 и 10 + 5 са два начина. Това е броят на поредиците, 48 007, а пакетите са 49. Когато банкнотите са външният цикъл, всеки пакет се строи в един ред и се брои веднъж.
Виж го
Измери го: рекурсия срещу таблица
Броим пробваните монети: във всяка рекурсия и във всяка клетка. Над 30 цента рекурсията не се пуска: при 40 цента са над 3 милиарда опита.
- Рекурсия без памет
O(2ⁿ) - Таблица
O(n)
| Алгоритъм | n = 10 | n = 20 | n = 30 |
|---|---|---|---|
| Рекурсия без памет | 309 | 66 281 | 14 158 888 |
| Таблица | 26 | 67 | 117 |
def change(coins, amount): best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return usedВсеки 10 цента умножават рекурсията около 200 пъти, а таблицата расте с 40–50 опита. Кривата на рекурсията е с етикет O(2ⁿ): тя е експоненциална, с основа около 1,7.
По-точно, за любопитните
Същите числа на твоя език:
tries = 0
def fewest(coins, amount): global tries if amount == 0: return 0 best = amount + 1 for coin in coins: if coin > amount: break tries += 1 count = fewest(coins, amount - coin) + 1 best = min(best, count) return best
def change(coins, amount): global tries best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break tries += 1 count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return used
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [10, 20, 30]: tries = 0 fewest(coins, amount) plain = tries tries = 0 change(coins, amount) print(f"{amount} цента: без памет {plain}, таблица {tries}")10 цента: без памет 309, таблица 2620 цента: без памет 66281, таблица 6730 цента: без памет 14158888, таблица 117Упражнение
Рестото от входа
Реши задачата в редактора си.
Ресто. Прочети рестото в центове и отпечатай колко монети връща автоматът и кои. Ползвай change от урока.
4805 монети: 10 + 20 + 50 + 200 + 200Още задачи
- Празна туба. Тубите с 1 и 2 цента са празни. Кои суми под 1 € автоматът изобщо не може да върне? Как го познаваш по таблицата? (Подсказка: клетката остава
amount + 1.) - Най-големите първо. Отпечатай монетите от най-голямата към най-малката.
- Колко начина с монети. По колко начина се плаща 1 € с монетите от 1 до 50 цента? А ако е позволена и монетата от 1 €?
По-точно
Невъзможно ресто и много големи числа
Две неща, които урокът прескочи.
По-точно, за любопитните
Когато рестото няма как да се върне. Ако тубите с 1 и 2 цента са празни, 3 цента не се връщат с нищо. Тогава клетката остава amount + 1, защото никой опит не е по-добър. Ако и last[a] е 0, връщането назад би се въртяло вечно на място. Затова преди връщането назад се проверява дали best[amount] > amount и автоматът казва „Няма ресто, платете точно“.
Броят начини расте много бързо. По колко начина се плащат 100 € само с монети (10 000 цента, осемте евро монети)?
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]
coins = [1, 2, 5, 10, 20, 50, 100, 200]print(ways(coins, 10000))1133873304647601long, а int щеше да прелее без грешка.Таблицата в две измерения. Броенето на начините всъщност е таблица „първите i банкноти × сумата“: клетка (i, a) е по колко начина се събира a само с първите i банкноти. Редът i се строи от реда над него (без банкнота i) и от клетката вляво в същия ред (с още една банкнота i). Програмата пази само един ред и го презаписва отляво надясно. Затова външният цикъл е по банкнотите: той върви по редовете. Същата идея, един ред вместо цялата таблица, идва пак в задачата за раницата.
Тест