Към съдържанието
wannacode

Кога алчният алгоритъм греши

Накратко: Алчният алгоритъм греши, когато най-добрият избор сега пречи на по-добър отговор после; един контрапример стига, а поправката често е динамично програмиране.

Проблем

Един ваучер повече

Магазинът изплаща точките за лоялност с ваучери от 4, 3 и 1 точка. Всеки ваучер е отделен код, който клиентът въвежда на касата. Затова програмата дава възможно най-малко ваучери: всеки път най-големия, който се побира, като рестото с евро монети в предния урок.

def greedy(vouchers, points):
    used = []
    for v in vouchers:
        while points >= v:
            used.append(v)
            points -= v
    return used
vouchers = [4, 3, 1]
print("6 точки: " + str(greedy(vouchers, 6)))
Изход
6 точки: [4, 1, 1]

Три кода за 6 точки. А 3 + 3 са два. Програмата не е сгрешила в кода: правилото „най-големия, който се побира“ просто не е вярно за тези ваучери. При евро монетите то е вярно, тук не е.

Идеята

Алчното не се връща назад

Алчният алгоритъм прави на всяка стъпка избора, който изглежда най-добър сега, и никога не го преразглежда. Взе ли 4, за останалите 2 точки има само ваучери от 1. Че 3 + 3 е по-добро, алчното не може да види: то не пробва нищо друго.

Затова алчна идея се приема само с доказателство, че локалният избор никога не вреди. А се отхвърля с един-единствен вход, на който дава по-лош отговор. Такъв вход се казва контрапример (counterexample). 6 точки е контрапример за алчното с ваучери 4, 3 и 1.

Едни и същи ваучери могат да са безопасни или опасни според стойностите си. 4, 2 и 1 са безопасни: всеки по-голям е кратен на по-малкия. 4, 3 и 1 не са.

Виж го

Алчното и DP едно до друго

Поправката е да не решаваш наведнъж, а да смяташ най-малкия брой ваучери за всяко количество от 0 до 6. За p точки пробваш всеки ваучер v като последен: остават p − v точки, а за тях най-малкото вече е сметнато. Това е динамичното програмиране за монетите, с таблица best. last пази кой ваучер е бил последен, за да се върнеш назад до самите ваучери.

def fewest(vouchers, points):
    best = [0] + [points + 1] * points
    last = [0] * (points + 1)
    for p in range(1, points + 1):
        for v in vouchers:
            if v <= p and best[p - v] + 1 < best[p]:
                best[p] = best[p - v] + 1
                last[p] = v
    used = []
    p = points
    while p > 0:
        used.append(last[p])
        p -= last[p]
    return used
vouchers = [4, 3, 1]
print(f"6 точки: алчно {greedy(vouchers, 6)}, най-малко {fewest(vouchers, 6)}")
print(f"10 точки: алчно {greedy(vouchers, 10)}, най-малко {fewest(vouchers, 10)}")
Изход
6 точки: алчно [4, 1, 1], най-малко [3, 3]
10 точки: алчно [4, 4, 1, 1], най-малко [4, 3, 3]

def fewest(vouchers, points):
    best = [0] + [points + 1] * points
    last = [0] * (points + 1)
    for p in range(1, points + 1):
        for v in vouchers:
            if v <= p and best[p - v] + 1 < best[p]:
                best[p] = best[p - v] + 1
                last[p] = v
    used = []
    p = points
    while p > 0:
        used.append(last[p])
        p -= last[p]
    return used
Стъпка по стъпка, с думи
  1. Алчно, 6 точки. Най-големият ваучер, който се побира, е 4: взима го. Остават 2 точки.
  2. Остават 2 точки: 4 и 3 не се побират. Взима 1. Остава 1 точка.
  3. Пак 1. Готово: 4 + 1 + 1, 3 ваучера. Изборът на 4 беше окончателен и затвори пътя към 3 + 3.
  4. DP смята най-малкото за всяко количество от 0 до 6. best[0] = 0: за 0 точки не трябва ваучер.
  5. best[1]: 1 → 1 + best[0] = 1. Най-малко 1, последен ваучер 1.
  6. best[2]: 1 → 1 + best[1] = 2. Най-малко 2, последен ваучер 1.
  7. best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. Най-малко 1, последен ваучер 3.
  8. best[4]: 4 → 1 + best[0] = 1; 3 → 1 + best[1] = 2; 1 → 1 + best[3] = 2. Най-малко 1, последен ваучер 4.
  9. best[5]: 4 → 1 + best[1] = 2; 3 → 1 + best[2] = 3; 1 → 1 + best[4] = 2. Най-малко 2, последен ваучер 4.
  10. best[6]: 4 → 1 + best[2] = 3; 3 → 1 + best[3] = 2; 1 → 1 + best[5] = 3. Най-малко 2, последен ваучер 3.
  11. Назад по last: 6 → 3 → 0. Ваучерите са 3 и 3: 2.
  12. Едно и също количество, два отговора: алчното дава 3 ваучера, DP дава 2. Алчното не се връща към избора си, а DP пробва всеки последен ваучер за всяко количество.

DP прави повече работа: количества × ваучери, тоест O(n·k), а алчното е колкото взетите ваучери. Но DP е вярно за всякакви ваучери, а алчното само за някои.

„Безкрайността“ в best е points + 1: повече от всеки истински отговор, защото с ваучер от 1 точка отговорът е най-много points. В Python може и float("inf"): inf + 1 си е inf. В Java и C# MAX_VALUE + 1 прелива в отрицателно число, затова там points + 1 е задължително, а тук е по избор.

Пробвай

Предвиди

Същите ваучери, 10 точки. Какво дава алчното?

def greedy(vouchers, points):
    used = []
    for v in vouchers:
        while points >= v:
            used.append(v)
            points -= v
    return used




vouchers = [4, 3, 1]
print(greedy(vouchers, 10))
Отговор

Пробвай

Попълни

За p точки с последен ваучер v: от кое количество идва останалото?

def fewest(vouchers, points):
    best = [0] + [points + 1] * points
    last = [0] * (points + 1)
    for p in range(1, points + 1):
        for v in vouchers:
            if v <= p and best[p - v] + 1 < best[p]:
                best[p] = best[] + 1
                last[p] = v
    used = []
    p = points
    while p > 0:
        used.append(last[p])
        p -= last[p]
    return used

Виж го

Раницата по такса на килограм

Куриерът има място за 10 кг. Чакат три пратки: 6 кг с такса 30 €, и две по 5 кг с такса по 20 €. Алчната идея: подреди пратките по такса на килограм и взимай, докато се побират.

def by_ratio(parcels, capacity):
    total = 0
    for kg, fee in sorted(parcels, key=lambda p: p[1] / p[0], reverse=True):
        if kg <= capacity:
            capacity -= kg
            total += fee
    return total




def best_fee(parcels, i, capacity):
    if i == len(parcels):
        return 0
    skip = best_fee(parcels, i + 1, capacity)
    kg, fee = parcels[i]
    if kg > capacity:
        return skip
    take = fee + best_fee(parcels, i + 1, capacity - kg)
    return max(skip, take)
parcels = [(6, 30), (5, 20), (5, 20)]
print(f"По такса на килограм: {by_ratio(parcels, 10)} €")
print(f"Най-добре: {best_fee(parcels, 0, 10)} €")
Изход
По такса на килограм: 30 €
Най-добре: 40 €

6-килограмовата е 5 € на кг, другите са по 4 € на кг. Алчното я взима първа, и останалите 4 кг не стигат за нищо. Двете по 5 кг пълнят колата точно и носят 40 €. bestFee пробва всяко подмножество: за всяка пратка „вземи“ или „пропусни“. Това е 2ⁿ, и за истински брой пратки трябва DP за раницата.

p[1] / p[0] в Python 3 е истинско делене с дробна част. // би било целочислено: 7 € за 2 кг ще стане 3 € на кг вместо 3,5.
По-точно, за любопитните

Ако пратките могат да се делят, алчното по такса на килограм е вярно. Така е с насипна стока: кафе на зърна, брашно, гориво. Взимаш колкото се побира от най-скъпото на килограм, после от следващото, а последното го режеш. Това е дробната раница (fractional knapsack), и там никой локален избор не затваря по-добър път.

Цялата пратка не се реже. Точно това прави алчното опасно: 6 кг заемат място, което двете по 5 кг биха ползвали по-добре.

Идеята

Как проверяваш алчна идея

Алчната идея звучи вярно почти винаги. Как разбираш дали е? Търсиш контрапример, но не на ръка, а с програма:

  1. Напиши бавно, но сигурно вярно решение: пълно изброяване (brute force), което пробва всички възможности.
  2. Пусни алчното и изброяването върху всички малки входове: всяко количество от 1 до 100.
  3. Първото място, където се разминават, е контрапример. Ако не се разминават никъде, не си доказал нищо, но имаш основание да търсиш доказателство.

Изброяването тук пробва колко от всяка монета да вземеш: от 0 до колкото се побират, рекурсивно за следващата. Последната монета е 1, и тя покрива каквото остане.

def try_all(coins, i, amount):
    if i == len(coins) - 1:
        return amount
    best = float("inf")
    for k in range(amount // coins[i] + 1):
        rest = try_all(coins, i + 1, amount - k * coins[i])
        best = min(best, k + rest)
    return best




def check(name, coins, up_to):
    for a in range(1, up_to + 1):
        g = len(greedy(coins, a))
        b = try_all(coins, 0, a)
        if g != b:
            print(f"{name}: {a} → алчно {g}, най-малко {b}")
            return
    print(f"{name}: до {up_to} няма контрапример")
check("Ваучери 4, 3, 1", [4, 3, 1], 20)
check("Евро монети", [200, 100, 50, 20, 10, 5, 2, 1], 100)
check("Стари британски", [30, 24, 12, 6, 3, 1], 100)
Изход
Ваучери 4, 3, 1: 6 → алчно 3, най-малко 2
Евро монети: до 100 няма контрапример
Стари британски: 48 → алчно 3, най-малко 2

Трите системи за секунда:

  • ваучерите 4, 3 и 1 падат на 6;
  • евро монетите в центове (1, 2, 5, 10, 20, 50 цента, 1 и 2 €) не падат до 100 цента;
  • старите британски монети в пенсове (1, 3, 6, 12, 24 и 30, част от системата преди 1971 г.) падат на 48: алчното дава 30 + 12 + 6, а 24 + 24 са две.

Изброяването е експоненциално и за големи входове е безнадеждно. Но контрапримерите почти винаги са малки, а малките входове то минава мигновено.

Пробвай

Намери грешката

Колегата пусна проверката за ваучерите и обяви, че алчното е вярно. Ти знаеш, че 6 е контрапример. Къде е грешката?

check("Ваучери 4, 3, 1", [4, 3, 1], 5)
check("Евро монети", [200, 100, 50, 20, 10, 5, 2, 1], 100)
check("Стари британски", [30, 24, 12, 6, 3, 1], 100)
Изход
Ваучери 4, 3, 1: до 5 няма контрапример
Евро монети: до 100 няма контрапример
Стари британски: 48 → алчно 3, най-малко 2

Избери реда с грешката.

По-точно, за любопитните

Докъде да проверяваш. За монети и ваучери има точен отговор (Kozen и Zaks, 1994): ако алчното някъде греши, най-малкият контрапример е по-малък от сбора на двете най-големи стойности. Значи пълна проверка дотам е доказателство:

  • ваучерите 4, 3 и 1: до 7;
  • евро монетите: до 300 цента (2 € + 1 €). Пусната до 300, проверката не намира контрапример, значи алчното е вярно за евро монетите при всяка сума;
  • старите британски: до 54 (30 + 24), а 48 е под тази граница.
Евро монети до 300 цента
Евро монети: до 300 няма контрапример

До 300 изброяването прави около 26 милиона извиквания и пак свършва за секунди. За по-голям обхват по-добрата проверка е DP вместо изброяването: то също е сигурно вярно, а е O(сума × монети).

За други задачи такава граница обикновено няма. Тогава проверката на малки входове не доказва, а само търси. Доказателството е разсъждение: най-често, че всяко оптимално решение може да се смени стъпка по стъпка в алчното, без да стане по-лошо.

Упражнение

Новите ваучери на маркетинга

Реши задачата в редактора си.

Новите ваучери. Маркетингът иска ваучери от 9, 6, 5 и 1 точка и пита дали касата може да остане алчна. Ползвай проверката от урока (greedy, изброяването и check) за количества до 30 точки и намери най-малкия контрапример.

Изход
Ваучери 9, 6, 5, 1: 11 → алчно 3, най-малко 2

Още задачи

  • Поправи системата. Кой ваучер да добавиш към 4, 3 и 1, за да стане алчното вярно до 7? Пробвай с проверката.
  • Раницата с проверка. Напиши проверка за раницата: алчното по такса на килограм срещу bestFee за всички комбинации от три пратки с тегла от 1 до 6 кг и такси от 1 до 9 €. Колко контрапримера намира?
  • Срокове. Задачите са с продължителност и срок. Алчното „най-кратката първа“ спазва ли най-много срокове? Намери контрапример с изброяване на всички подредби на 4 задачи.

Тест

Провери се

1. Ваучерите са от 4, 3 и 1 точка. Колко ваучера дава алчното за 6 точки и колко е най-малкото?
2. Алчна идея мина 50 теста. Какво доказва това?
3. Куриерът има място за 10 кг. Пратки: 6 кг за 30 €, 5 кг за 20 € и 5 кг за 20 €. Какво взима алчното по такса на килограм?
4. Защо в DP за ваучерите „безкрайността“ е points + 1, а не Integer.MAX_VALUE в Java?
5. Проверката търси контрапример за ваучерите 4, 3 и 1 само до 5 точки и не намира. Защо?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·