Açgözlü seçim ve tuttuğu yer

Açgözlü yöntem her adımda o an en iyi görüneni seçer ve bir daha dönüp bakmaz. Hızlıdır ve yazması kolaydır. Zor olan, seçimin gerçekten zararsız olduğunu görmektir: bazı problemlerde yerel en iyi, bütünün en iyisine götürür; bazılarında götürmez.

1fives = tens = 0
2for bill in bills:
3    if bill == 5:
4        fives += 1
5    elif bill == 10:
6        fives -= 1
7        tens += 1
8    elif tens > 0:
9        tens -= 1
10        fives -= 1
11    else:
12        fives -= 3
13    if fives < 0:
14        return False
15return True

Açgözlü bir çözüm yazmadan önce onu çürütmeye çalış: seçimin kötü sonuç vereceği küçük bir girdi arar ve bulamazsan muhtemelen doğrudur. Bozuk parada bu girdi vardır: 1, 3 ve 4'lük paralarla 6'yı "en büyük parayı al" kuralı üç parayla yapar, doğrusu iki paradır.