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

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

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

Проблем

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

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

static List<Integer> greedy(int[] vouchers, int points) {
    List<Integer> used = new ArrayList<>();
    for (int v : vouchers) {
        while (points >= v) {
            used.add(v);
            points -= v;
        }
    }
    return used;
}
int[] vouchers = {4, 3, 1};
System.out.println("6 точки: " + 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 пази кой ваучер е бил последен, за да се върнеш назад до самите ваучери.

static List<Integer> fewest(int[] vouchers, int points) {
    int[] best = new int[points + 1];
    int[] last = new int[points + 1];
    for (int p = 1; p <= points; p++) {
        best[p] = points + 1;
        for (int v : vouchers) {
            if (v <= p && best[p - v] + 1 < best[p]) {
                best[p] = best[p - v] + 1;
                last[p] = v;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int p = points; p > 0; p -= last[p]) {
        used.add(last[p]);
    }
    return used;
}
int[] vouchers = {4, 3, 1};
System.out.println("6 точки: алчно " + greedy(vouchers, 6) + ", най-малко " + fewest(vouchers, 6));
System.out.println("10 точки: алчно " + greedy(vouchers, 10) + ", най-малко " + fewest(vouchers, 10));
Изход
6 точки: алчно [4, 1, 1], най-малко [3, 3]
10 точки: алчно [4, 4, 1, 1], най-малко [4, 3, 3]

static List<Integer> fewest(int[] vouchers, int points) {
    int[] best = new int[points + 1];
    int[] last = new int[points + 1];
    for (int p = 1; p <= points; p++) {
        best[p] = points + 1;
        for (int v : vouchers) {
            if (v <= p && best[p - v] + 1 < best[p]) {
                best[p] = best[p - v] + 1;
                last[p] = v;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int p = points; p > 0; p -= last[p]) {
        used.add(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. Integer.MAX_VALUE изглежда по-естествено, но best[p - v] + 1 би прелял в -2 147 483 648 и би спечелил сравнението.

Пробвай

Предвиди

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

static List<Integer> greedy(int[] vouchers, int points) {
    List<Integer> used = new ArrayList<>();
    for (int v : vouchers) {
        while (points >= v) {
            used.add(v);
            points -= v;
        }
    }
    return used;
}


int[] vouchers = {4, 3, 1};
System.out.println(greedy(vouchers, 10));
Отговор

Пробвай

Попълни

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

static List<Integer> fewest(int[] vouchers, int points) {
    int[] best = new int[points + 1];
    int[] last = new int[points + 1];
    for (int p = 1; p <= points; p++) {
        best[p] = points + 1;
        for (int v : vouchers) {
            if (v <= p && best[p - v] + 1 < best[p]) {
                best[p] = best[] + 1;
                last[p] = v;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int p = points; p > 0; p -= last[p]) {
        used.add(last[p]);
    }
    return used;
}

Виж го

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

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

static int byRatio(int[][] parcels, int capacity) {
    int[][] sorted = parcels.clone();
    Arrays.sort(sorted, (a, b) -> Double.compare((double) b[1] / b[0], (double) a[1] / a[0]));
    int total = 0;
    for (int[] p : sorted) {
        if (p[0] <= capacity) {
            capacity -= p[0];
            total += p[1];
        }
    }
    return total;
}


static int bestFee(int[][] parcels, int i, int capacity) {
    if (i == parcels.length) {
        return 0;
    }
    int skip = bestFee(parcels, i + 1, capacity);
    if (parcels[i][0] > capacity) {
        return skip;
    }
    int take = parcels[i][1] + bestFee(parcels, i + 1, capacity - parcels[i][0]);
    return Math.max(skip, take);
}
int[][] parcels = {{6, 30}, {5, 20}, {5, 20}};
System.out.println("По такса на килограм: " + byRatio(parcels, 10) + " €");
System.out.println("Най-добре: " + bestFee(parcels, 0, 10) + " €");
Изход
По такса на килограм: 30 €
Най-добре: 40 €

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

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

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

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

Идеята

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

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

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

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

static int tryAll(int[] coins, int i, int amount) {
    if (i == coins.length - 1) {
        return amount;
    }
    int best = Integer.MAX_VALUE;
    for (int k = 0; k * coins[i] <= amount; k++) {
        int rest = tryAll(coins, i + 1, amount - k * coins[i]);
        best = Math.min(best, k + rest);
    }
    return best;
}


static void check(String name, int[] coins, int upTo) {
    for (int a = 1; a <= upTo; a++) {
        int g = greedy(coins, a).size();
        int b = tryAll(coins, 0, a);
        if (g != b) {
            System.out.println(name + ": " + a + " → алчно " + g + ", най-малко " + b);
            return;
        }
    }
    System.out.println(name + ": до " + upTo + " няма контрапример");
}
check("Ваучери 4, 3, 1", new int[] {4, 3, 1}, 20);
check("Евро монети", new int[] {200, 100, 50, 20, 10, 5, 2, 1}, 100);
check("Стари британски", new int[] {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", new int[] {4, 3, 1}, 5);
check("Евро монети", new int[] {200, 100, 50, 20, 10, 5, 2, 1}, 100);
check("Стари британски", new int[] {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 за достъпно обучение по програмиране ·