Kako vratiti ostatak s najmanje kovanica? Uzmi najveću koja stane. Ponekad je najbolja strategija baš ona najjednostavnija, ali samo ponekad.
Pythonoko 45 minuta4 zadatka za evaluator
1Uzmi ono što je sada najbolje
Prodavač treba vratiti 87 centi s što manje kovanica. Što bi učinio svaki prodavač? Uzme najveću kovanicu koja stane, pa opet najveću koja stane, i tako dok ne vrati sve. Takav pristup, u kojem u svakom koraku uzmemo ono što je trenutno najbolje, zove se pohlepni algoritam (engl. greedy).
k–
iznos–
broj–
Klikni „Sljedeći korak“ i prati što se događa.
2Kad pohlepno ne radi
Zvuči previše jednostavno da bi uvijek bilo točno. I nije! Zamisli izmišljenu zemlju s kovanicama od 1, 3 i 4 dukata i iznos od 6 dukata.
Pristup
Kovanice
Broj kovanica
pohlepno: najveća koja stane
4 + 1 + 1
3
najbolje
3 + 3
2
Pazi
Pohlepni algoritam je brz i jednostavan, ali nije uvijek točan. Prije nego ga upotrijebiš, uvjeri se da radi: potraži primjer u kojem bi pogriješio. Za kovanice eura pohlepno uvijek daje najmanji broj kovanica, a za kovanice 1, 3 i 4 ne daje.
Ključna ideja
Dobar način provjere: za male ulaze usporedi pohlepno rješenje s rješenjem grubom silom iz lekcije 23. Ako se negdje razlikuju, pohlepni algoritam nije dobar.
3Sortiraj, pa uzimaj
Većina pohlepnih rješenja počinje sortiranjem. Primjer: s džeparcem od B eura želimo kupiti što više igračaka. Pohlepno je jasno: kupuj od najjeftinije.
n, b = map(int, input().split())
cijene = sorted(map(int, input().split()))
kupljeno = 0for c in cijene:
if c > b:
break
b -= c
kupljeno += 1print(kupljeno)
Ulaz
5 20
7 3 10 2 4
Ispis
4
Zašto je ovo točno? Kad bi u kupnji bila skuplja igračka umjesto neke jeftinije koju nismo uzeli, zamjenom bismo uštedjeli novac, a broj igračaka ostao bi isti. Zato je uvijek dobro uzeti najjeftinije.
4Raspored: što više događaja
U dvorani je dan pun prijava za događaje. Za svaki znamo početak i kraj, a u dvorani istodobno može biti samo jedan. Kako odabrati što više događaja?
Pohlepno pravilo koje radi: uvijek uzmi događaj koji najranije završi, a zatim od preostalih koji počinju nakon njega opet onaj koji najranije završi. Što prije dvorana bude slobodna, to više mjesta ostaje za ostale.
n = int(input())
d = []
for i inrange(n):
s, e = map(int, input().split())
d.append((e, s))
d.sort()
slobodno_od = 0
odabrano = 0for kraj, pocetak in d:
if pocetak >= slobodno_od:
odabrano += 1
slobodno_od = kraj
print(odabrano)
Ulaz
5
1 4
3 5
0 6
5 7
8 9
Ispis
3
Ključna ideja
Događaje spremamo kao n-torke (kraj, početak) iz lekcije 24, jer se lista n-torki sortira po prvom elementu, a nama treba sortiranje po kraju.
Stani i razmisli
Zašto ne uzeti najkraći događaj ili onaj koji najranije počne?
Pogledaj odgovor
Oba pravila mogu pogriješiti. Događaj od 0 do 100 počinje najranije, ali blokira cijeli dan. Kratki događaj od 4 do 6 može prekinuti dva duža koja bi inače oba stala, npr. od 0 do 5 i od 5 do 10. Pravilo „najraniji kraj“ nema takvu zamku.
Na natjecanju
Prije nego predaš pohlepno rješenje, isprobaj ga na nekoliko malih primjera koje možeš riješiti i ručno. Ako nađeš protuprimjer, treba drugi pristup.
5Provjeri se
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Pitanje
Što je pohlepni algoritam?
Lokalno najbolji izbor u svakom koraku.
Pitanje
Daje li pohlepni pristup uvijek točan rezultat?
Ponekad ne: isprobaj male primjere.
Pitanje
Za najviše nepreklapajućih događaja, po čemu sortiramo?
Uzimamo događaj koji najranije završi.
6Zadaci
Kovanice
★☆☆ lagano
Prodavač vraća ostatak kovanicama eura: 200, 100, 50, 20, 10, 5, 2 i 1 cent. Koliko najmanje kovanica treba za zadani iznos?
Ulaz
Jedan cijeli broj, iznos u centima.
Izlaz
Najmanji broj kovanica.
Ograničenja
1 ≤ iznos ≤ 1 000 000
Ulaz
87
Izlaz
5
Ulaz
400
Izlaz
2
Treba ti pomoć?
Umjesto da kovanicu oduzimaš jednu po jednu, broj kovanica iste vrijednosti dobiješ s //, a ostatak s %.
U knjižnici čeka N učenika. Za svakog znamo koliko minuta traje njegovo posuđivanje. Učenik čeka dok se ne posluže svi ispred njega. Kojim redoslijedom treba posluživati da ukupno čekanje svih učenika bude najmanje? Ispiši to najmanje ukupno čekanje.
Ulaz
U prvom retku N. U drugom retku N trajanja u minutama.
Izlaz
Najmanje ukupno čekanje.
Ograničenja
1 ≤ N ≤ 100 000, trajanja od 1 do 1000
Ulaz
3
5 1 3
Izlaz
5
Treba ti pomoć?
U primjeru je najbolji red 1, 3, 5: prvi čeka 0, drugi 1, treći 1 + 3 = 4 minute, ukupno 5. Tko bi trebao ići prvi: brži ili sporiji?
Za dvoranu je stiglo N prijava. Svaki događaj ima početak i kraj. Događaj koji počinje točno kad drugi završi smije se održati. Koliko najviše događaja možemo prihvatiti?
Ulaz
U prvom retku N. U svakom od sljedećih N redaka početak i kraj jednog događaja.
Izlaz
Najveći broj događaja.
Ograničenja
1 ≤ N ≤ 100 000, 0 ≤ početak < kraj ≤ 10⁹
Ulaz
5
1 4
3 5
0 6
5 7
8 9
Izlaz
3
Treba ti pomoć?
Pravilo iz dijela 4: najraniji kraj. Spremi događaje kao parove (kraj, početak) i sortiraj.