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

Проблем

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

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

function greedy(vouchers, points) {
  const used = [];
  for (const v of vouchers) {
    while (points >= v) {
      used.push(v);
      points -= v;
    }
  }
  return used;
}

const vouchers = [4, 3, 1];
console.log("6 точки: " + "[" + greedy(vouchers, 6).join(", ") + "]");

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 пази кой ваучер е бил последен, за да се върнеш назад до самите ваучери.

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[p - v] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}

const vouchers = [4, 3, 1];
console.log("6 точки: алчно " + "[" + greedy(vouchers, 6).join(", ") + "]" + ", най-малко " + "[" + fewest(vouchers, 6).join(", ") + "]");
console.log("10 точки: алчно " + "[" + greedy(vouchers, 10).join(", ") + "]" + ", най-малко " + "[" + fewest(vouchers, 10).join(", ") + "]");

6 точки: алчно [4, 1, 1], най-малко [3, 3]
10 точки: алчно [4, 4, 1, 1], най-малко [4, 3, 3]

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[p - v] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}

Стъпка по стъпка, с думи

Алчно, 6 точки. Най-големият ваучер, който се побира, е 4: взима го. Остават 2 точки.
Остават 2 точки: 4 и 3 не се побират. Взима 1. Остава 1 точка.
Пак 1. Готово: 4 + 1 + 1, 3 ваучера. Изборът на 4 беше окончателен и затвори пътя към 3 + 3.
DP смята най-малкото за всяко количество от 0 до 6. best[0] = 0: за 0 точки не трябва ваучер.
best[1]: 1 → 1 + best[0] = 1. Най-малко 1, последен ваучер 1.
best[2]: 1 → 1 + best[1] = 2. Най-малко 2, последен ваучер 1.
best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. Най-малко 1, последен ваучер 3.
best[4]: 4 → 1 + best[0] = 1; 3 → 1 + best[1] = 2; 1 → 1 + best[3] = 2. Най-малко 1, последен ваучер 4.
best[5]: 4 → 1 + best[1] = 2; 3 → 1 + best[2] = 3; 1 → 1 + best[4] = 2. Най-малко 2, последен ваучер 4.
best[6]: 4 → 1 + best[2] = 3; 3 → 1 + best[3] = 2; 1 → 1 + best[5] = 3. Най-малко 2, последен ваучер 3.
Назад по last: 6 → 3 → 0. Ваучерите са 3 и 3: 2.
Едно и също количество, два отговора: алчното дава 3 ваучера, DP дава 2. Алчното не се връща към избора си, а DP пробва всеки последен ваучер за всяко количество.

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

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

Пробвай

Предвиди

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

function greedy(vouchers, points) {
  const used = [];
  for (const v of vouchers) {
    while (points >= v) {
      used.push(v);
      points -= v;
    }
  }
  return used;
}

const vouchers = [4, 3, 1];
console.log("[" + greedy(vouchers, 10).join(", ") + "]");

Отговор

[4, 3, 3]

[3, 3, 4]

[4, 4, 1, 1]

Пробвай

Попълни

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

function fewest(vouchers, points) {
  const best = [0];
  const last = [0];
  for (let p = 1; p <= points; p++) {
    best[p] = points + 1;
    last[p] = 0;
    for (const v of vouchers) {
      if (v <= p && best[p - v] + 1 < best[p]) {
        best[p] = best[] + 1;
        last[p] = v;
      }
    }
  }
  const used = [];
  for (let p = points; p > 0; p -= last[p]) {
    used.push(last[p]);
  }
  return used;
}

Виж го

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

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

function byRatio(parcels, capacity) {
  const sorted = [...parcels].sort((a, b) => b[1] / b[0] - a[1] / a[0]);
  let total = 0;
  for (const [kg, fee] of sorted) {
    if (kg <= capacity) {
      capacity -= kg;
      total += fee;
    }
  }
  return total;
}

function bestFee(parcels, i, capacity) {
  if (i === parcels.length) {
    return 0;
  }
  const skip = bestFee(parcels, i + 1, capacity);
  const [kg, fee] = parcels[i];
  if (kg > capacity) {
    return skip;
  }
  const take = fee + bestFee(parcels, i + 1, capacity - kg);
  return Math.max(skip, take);
}

const parcels = [[6, 30], [5, 20], [5, 20]];
console.log(`По такса на килограм: ${byRatio(parcels, 10)} €`);
console.log(`Най-добре: ${bestFee(parcels, 0, 10)} €`);

По такса на килограм: 30 €
Най-добре: 40 €

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

b[1] / b[0] в JavaScript винаги дава дробно число. В Java и C# делението на две цели числа е целочислено, и там трябва (double).

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

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

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

Идеята

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

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

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

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

function tryAll(coins, i, amount) {
  if (i === coins.length - 1) {
    return amount;
  }
  let best = Infinity;
  for (let k = 0; k * coins[i] <= amount; k++) {
    const rest = tryAll(coins, i + 1, amount - k * coins[i]);
    best = Math.min(best, k + rest);
  }
  return best;
}

function check(name, coins, upTo) {
  for (let a = 1; a <= upTo; a++) {
    const g = greedy(coins, a).length;
    const b = tryAll(coins, 0, a);
    if (g !== b) {
      console.log(`${name}: ${a} → алчно ${g}, най-малко ${b}`);
      return;
    }
  }
  console.log(`${name}: до ${upTo} няма контрапример`);
}

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 изброяването прави около 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, най-малкото 3И двете 2Алчното 3 (4 + 1 + 1), най-малкото 2 (3 + 3)

2. Алчна идея мина 50 теста. Какво доказва това?Нищо: един контрапример стига, за да е грешнаЧе е вярна поне за входове до 50Че е вярна за всеки вход

3. Куриерът има място за 10 кг. Пратки: 6 кг за 30 €, 5 кг за 20 € и 5 кг за 20 €. Какво взима алчното по такса на килограм?Двете по 5 кг: 40 €И трите: 70 €Само 6-килограмовата: 30 €

4. Защо в DP за ваучерите „безкрайността“ е points + 1, а не Integer.MAX_VALUE в Java?MAX_VALUE е бавенДвете са еднаквиMAX_VALUE + 1 прелива в отрицателно число и минава за най-малкото

5. Проверката търси контрапример за ваучерите 4, 3 и 1 само до 5 точки и не намира. Защо?Алчното е вярно до 5, значи е вярно винагиНай-малкият контрапример е 6: обхватът е твърде малъкПълното изброяване греши при малки числа

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

Бисквитки