Задачата за монетите

Код на:JavaC#PythonJavaScript

Накратко: Задачата за монетите търси най-малко монети за дадена сума; таблицата на динамичното програмиране я решава за O(сума × монети), казва кои са монетите и брои начините.

Проблем

Рестото на автомата

Автоматът на паркинга връща ресто. Има по една туба за всяка от осемте евро монети: 1, 2, 5, 10, 20 и 50 цента, 1 € и 2 €. Колкото по-малко монети връща, толкова по-рядко някой трябва да зарежда тубите. Затова рестото трябва да е с най-малко монети.

Програмистът не иска да гадае и пише рекурсия, която пробва всичко: за всяка монета, която се събира в рестото, „тази монета плюс най-доброто за остатъка“, и взима най-малкото. Сумите са в центове, а броячът брои пробваните монети:

let tries = 0;

function fewest(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  let best = amount + 1;
  for (const coin of coins) {
    if (coin > amount) {
      break;
    }
    tries++;
    const count = fewest(coins, amount - coin) + 1;
    best = Math.min(best, count);
  }
  return best;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [10, 20, 30]) {
  tries = 0;
  const count = fewest(coins, amount);
  console.log(`${amount} цента: ${count} монети, ${tries} опита`);
}

Изход

10 цента: 1 монети, 309 опита
20 цента: 1 монети, 66281 опита
30 цента: 2 монети, 14158888 опита

Отговорите са верни. Но за 30 цента рекурсията пробва 14 158 888 монети, а за 40 цента 3 024 560 419. Рестото от 63 цента иска 689 951 222 249 236 опита: при милиард в секунда това са осем дни, докато шофьорът чака на бариерата.

Идеята

Таблицата

Рекурсията пита отново и отново едно и също: най-доброто за 13 цента, за 8 цента, за 3 цента. Това са припокриващите се подзадачи от предишния урок. Само че тук от всяка сума излизат до осем клона, по един за всяка монета, и дървото расте още по-бързо.

Затова строим таблица отдолу нагоре. Една таблица за динамично програмиране се описва с четири неща:

• Какво значи клетката. best[a] е най-малкият брой монети за точно a цента.
• Откъде идва. Последната монета е някоя от тези, които се събират. Значи best[a] е 1 + best[a − монета] за най-добрата монета.
• В какъв ред се пълни. a − монета е по-малко от a. Отляво надясно всичко, което клетката чете, вече е готово.
• Къде е отговорът. В последната клетка, best[рестото]. Началото е best[0] = 0: нула цента не искат монети.

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

Виж го

Клетка по клетка

Таблицата за 9 цента. Гледай стрелките: всяка идва от клетката a − монета, а клетката a пази най-малкото, което е видяла:

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

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

1. change(coins, 9): best[a] е най-малкият брой монети за a цента, last[a] е монетата, с която се стига дотам. best[0] = 0: нула цента не искат монети.
2. За всяко a отляво надясно пробвай всяка монета до a: една монета плюс най-доброто за остатъка, best[a − монета] + 1. Стрелката идва от тази клетка.
3. a = 5: монетата 1 дава best[4] + 1 = 3, монетата 2 дава best[3] + 1 = 3, монетата 5 дава best[0] + 1 = 1. Клетката пази най-малкото, а last помни монетата.
4. Монетите са подредени от малката към голямата, а 10 вече е повече от 9: цикълът спира там. Всяка клетка чете само клетки вляво от нея, а те вече са окончателни.
5. Назад по last: 9 → 7 → 5 → 0. Монетите са 2 + 2 + 5. 22 опита за 9 цента, всяка клетка решена веднъж.

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
console.log(change(coins, 9));

Изход

[ 2, 2, 5 ]

amount + 1 е „още нищо“: повече монети от центовете няма как да трябват, защото и с еднецентови стигат точно amount. Затова първата пробвана монета винаги е по-добра.

Идеята

Кои монети

Броят не стига: автоматът трябва да знае и кои монети да пусне. Затова до best[a] таблицата пази и last[a], монетата, с която се стига до най-доброто за a. Накрая тръгваш от рестото: пускаш last[a], вадиш я, и повтаряш, докато стигнеш 0.

let tries = 0;

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      tries++;
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [63, 480]) {
  tries = 0;
  const used = change(coins, amount);
  console.log(`${amount} цента: ${used.join(" + ")}, ${tries} опита`);
}

Изход

63 цента: 1 + 2 + 10 + 50, 296 опита
480 цента: 10 + 20 + 50 + 200 + 200, 3460 опита

296 опита за 63 цента вместо 689 951 222 249 236. Таблицата има по една клетка на цент, а всяка клетка пробва най-много осемте монети. Работата е O(n · k): n цента по k вида монети. С k = 8 това е линейно в рестото.

Пробвай

Попълни

Една монета плюс най-доброто за остатъка. Коя клетка чете опитът?

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Провери

Идеята

А защо не най-голямата монета първо?

Касиерът прави друго: дава най-голямата монета, която се събира, и повтаря. За 63 цента това е 50, 10, 2, 1: пак четири монети. С евро монетите това правило винаги дава най-малкия брой. Монетите са подбрани така.

Но правилото зависи от системата монети. При други монети, или когато в автомата свърши някоя туба, „най-голямата първо“ може да даде повече монети от нужното. Кога то работи и кога лъже, е урокът „Кога алчният алгоритъм греши“. Таблицата не разчита на това: тя пробва всяка монета за всяка сума и намира най-малкото при всякакви монети.

Идеята

По колко начина

Друга задача със същата таблица. Банкоматът изплаща суми с банкноти от 5, 10, 20 и 50 €. Тестерите искат да проверят всеки възможен пакет за 100 € и питат: колко са?

Сега клетката е count[a]: по колко начина се събират точно a евро. count[0] = 1, празният пакет. Външният цикъл е по банкнотите, вътрешният по сумите:

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const notes = [5, 10, 20, 50];
console.log(ways(notes, 100), "начина");

Изход

49 начина

Редът на циклите е важен. Когато петиците са изцяло преди десетиците, всеки пакет се сглобява в един ред: първо петиците, после десетиците. Затова 5 + 10 и 10 + 5 са един и същ пакет и се броят веднъж. И тук никой не търси минимум: клетката събира броя на начините от клетките вляво.

Пробвай

Предвиди изхода

Колко пакета има за 20 € с банкноти от 5, 10 и 20?

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const notes = [5, 10, 20];
console.log(ways(notes, 20), "начина");

Отговор

3 начина

6 начина

4 начина

Провери

Пробвай

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

Колега е написал същото броене, но за 100 € излиза много повече:

const notes = [5, 10, 20, 50];
console.log(ways(notes, 100), "начина");

Изход

48007 начина

На кой ред е грешката?

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

1function ways(notes, amount) {2 const count = new Array(amount + 1).fill(0);3 count[0] = 1;4 for (let a = 1; a <= amount; a++) {5 for (const note of notes) {6 if (note <= a) {7 count[a] += count[a - note];8 }9 }10 }11 return count[amount];12}

Провери

Виж го

Измери го: рекурсия срещу таблица

Броим пробваните монети: във всяка рекурсия и във всяка клетка. Над 30 цента рекурсията не се пуска: при 40 цента са над 3 милиарда опита.

• Рекурсия без памет O(2ⁿ)
• Таблица O(n)

Алгоритъм	n = 10	n = 20	n = 30
Рекурсия без памет	309	66 281	14 158 888
Таблица	26	67	117

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

Всеки 10 цента умножават рекурсията около 200 пъти, а таблицата расте с 40–50 опита. Кривата на рекурсията е с етикет O(2ⁿ): тя е експоненциална, с основа около 1,7.

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

Същите числа на твоя език:

let tries = 0;

function fewest(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  let best = amount + 1;
  for (const coin of coins) {
    if (coin > amount) {
      break;
    }
    tries++;
    const count = fewest(coins, amount - coin) + 1;
    best = Math.min(best, count);
  }
  return best;
}

function change(coins, amount) {
  const best = new Array(amount + 1).fill(0);
  const last = new Array(amount + 1).fill(0);
  for (let a = 1; a <= amount; a++) {
    best[a] = amount + 1;
    for (const coin of coins) {
      if (coin > a) {
        break;
      }
      tries++;
      const count = best[a - coin] + 1;
      if (count < best[a]) {
        best[a] = count;
        last[a] = coin;
      }
    }
  }
  const used = [];
  for (let a = amount; a > 0; a -= last[a]) {
    used.push(last[a]);
  }
  return used;
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
for (const amount of [10, 20, 30]) {
  tries = 0;
  fewest(coins, amount);
  const plain = tries;
  tries = 0;
  change(coins, amount);
  console.log(`${amount} цента: без памет ${plain}, таблица ${tries}`);
}

Изход

10 цента: без памет 309, таблица 26
20 цента: без памет 66281, таблица 67
30 цента: без памет 14158888, таблица 117

Упражнение

Рестото от входа

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

Ресто. Прочети рестото в центове и отпечатай колко монети връща автоматът и кои. Ползвай change от урока.

Вход

480

Изход

5 монети: 10 + 20 + 50 + 200 + 200

Още задачи

• Празна туба. Тубите с 1 и 2 цента са празни. Кои суми под 1 € автоматът изобщо не може да върне? Как го познаваш по таблицата? (Подсказка: клетката остава amount + 1.)
• Най-големите първо. Отпечатай монетите от най-голямата към най-малката.
• Колко начина с монети. По колко начина се плаща 1 € с монетите от 1 до 50 цента? А ако е позволена и монетата от 1 €?

По-точно

Невъзможно ресто и много големи числа

Две неща, които урокът прескочи.

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

Когато рестото няма как да се върне. Ако тубите с 1 и 2 цента са празни, 3 цента не се връщат с нищо. Тогава клетката остава amount + 1, защото никой опит не е по-добър. Ако и last[a] е 0, връщането назад би се въртяло вечно на място. Затова преди връщането назад се проверява дали best[amount] > amount и автоматът казва „Няма ресто, платете точно“.

Броят начини расте много бързо. По колко начина се плащат 100 € само с монети (10 000 цента, осемте евро монети)?

function ways(notes, amount) {
  const count = new Array(amount + 1).fill(0);
  count[0] = 1;
  for (const note of notes) {
    for (let a = note; a <= amount; a++) {
      count[a] += count[a - note];
    }
  }
  return count[amount];
}

const coins = [1, 2, 5, 10, 20, 50, 100, 200];
console.log(ways(coins, 10000));

Изход

1133873304647601

В JavaScript числото е с плаваща запетая и пази точно цели числа до 2⁵³, около 9 · 10¹⁵. Това число е под границата и е точно. За по-големи суми клетките трябва да са BigInt (0n, 1n), иначе отговорът тихо се закръгля.

Таблицата в две измерения. Броенето на начините всъщност е таблица „първите i банкноти × сумата“: клетка (i, a) е по колко начина се събира a само с първите i банкноти. Редът i се строи от реда над него (без банкнота i) и от клетката вляво в същия ред (с още една банкнота i). Програмата пази само един ред и го презаписва отляво надясно. Затова външният цикъл е по банкнотите: той върви по редовете. Същата идея, един ред вместо цялата таблица, идва пак в задачата за раницата.

Тест

Провери се

1. Какво значи клетката best[a] в таблицата на рестото?

Най-голямата монета, която се събира в aКолко монети от вида a има в автоматаНай-малкият брой монети, с които се плащат точно a цента

2. Защо таблицата се пълни отляво надясно, от a = 1 нагоре?

Редът няма значение, може и отдясно налявоКлетка a чете само клетки a − монета, които са вляво от нея и вече са окончателниЗащото монетите са подредени отляво надясно

3. Как таблицата казва кои са монетите, а не само колко са?

Брои колко пъти е ползвана всяка клеткаlast[a] помни монетата, с която се стига до най-доброто за a; от рестото назад по last излизат монетите една по еднаНе може: трябва втора таблица за всяка монета

4. В броенето на начините циклите са разменени: външният е по сумите, вътрешният по банкнотите. Какво става?

Брои по-малко начиниБрои поредици: 5 + 10 и 10 + 5 стават два начина, затова числото е много по-голямоНищо, отговорът е същият

5. С евро монетите „най-голямата монета, която се събира, и пак“ дава най-малкия брой. Защо тогава таблица?

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

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Big-O: как расте работата · Сложност по памет · Разделяй и владей и дървото на рекурсията · Припокриващи се подзадачи
• Продължава в: Задачата за раницата · Най-дълга обща подредица и diff · Как да разпознаеш DP задача · Алчният алгоритъм и кога работи
• Задачи по темата: Динамично програмиране