Задачата за раницата в JavaScript

Проблем

Кои колети в кутията

Куриер кара товарен велосипед, а кутията му носи до 50 кг. В склада го чакат колети. Всеки има тегло и такса за доставка, а куриерът получава таксата за всеки доставен колет. Колет не се разделя: взима се цял или изобщо не се взима. Кои колети да вземе, за да изкара най-много?

Програмистът пробва всичко: за всеки колет „взимам“ или „не взимам“. Когато е решил за всички, проверява дали товарът се събира и колко носи. Колетите идват от склада. Тук ги строим с формула, за да са едни и същи на всеки език: тегло от 1 до 20 кг, такса от 2 до 40 €.

let tries = 0;

function tryAll(weight, fee, cap, i, load, sum) {
  if (i === weight.length) {
    tries++;
    return load <= cap ? sum : -1;
  }
  const skip = tryAll(weight, fee, cap, i + 1, load, sum);
  const take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]);
  return Math.max(skip, take);
}

for (const n of [10, 20]) {
  const weight = [];
  const fee = [];
  for (let i = 0; i < n; i++) {
    weight.push(1 + i * 7 % 20);
    fee.push(2 + i * 11 % 39);
  }
  tries = 0;
  const best = tryAll(weight, fee, 50, 0, 0, 0);
  console.log(`${n} колета: ${best} €, ${tries} комбинации`);
}

10 колета: 169 €, 1024 комбинации
20 колета: 208 €, 1048576 комбинации

Всеки колет удвоява комбинациите: 10 колета са 1024, 20 са над милион. При 30 колета са над милиард, а при 50 колета са 1 125 899 906 842 624. С милиард комбинации в секунда това са около 13 дни, а куриерът тръгва в осем сутринта.

Идеята

Таблица колети × килограми

В рекурсията се повтарят едни и същи въпроси: „най-доброто от колет 7 нататък с 23 кг място“ идва по много различни пътища. Памет по двойката (колет, място) би спряла повторенията. Но и тук таблицата отдолу нагоре е по-проста и вече я знаеш. Само че тук подзадачата има две числа: колко колета гледаш и колко килограма място имаш. Таблицата е двумерна.

Четирите неща на таблицата:

Какво значи клетката. best[i][w] е най-голямата такса с първите i колета и товар до w кг.
Откъде идва. Колет i или не е вътре, и тогава е best[i − 1][w]. Или е вътре: таксата му плюс best[i − 1][w − теглото му], най-доброто без него за останалите килограми. Клетката пази по-голямото.
В какъв ред се пълни. Ред по ред: всеки ред чете само горния.
Къде е отговорът. Долу вдясно: всички колети, целият товар. Началото е редът 0, без колети: навсякъде 0.

Това е задачата за раницата (0/1 knapsack): неща с тегло и стойност, място с ограничение, и всяко нещо се взима цяло или не се взима. С нея се избират колети за курс, задачи за спринт с ограничени часове, реклами за ограничено ефирно време.

Виж го

Вземи или остави

Последният курс за деня: в кутията остават 6 кг място и чакат четири колета. Гледай двете клетки, които всяка клетка чете: горната („остави“) и стрелката от горния ред с таксата („вземи“):

function pack(weight, fee, cap) {
  const n = weight.length;
  const best = [];
  for (let i = 0; i <= n; i++) {
    best.push(new Array(cap + 1).fill(0));
  }
  for (let i = 1; i <= n; i++) {
    const kg = weight[i - 1];
    const paid = fee[i - 1];
    for (let w = 0; w <= cap; w++) {
      best[i][w] = best[i - 1][w];
      if (kg <= w) {
        const take = best[i - 1][w - kg] + paid;
        best[i][w] = Math.max(best[i][w], take);
      }
    }
  }
  const taken = [];
  for (let i = n, w = cap; i > 0; i--) {
    if (best[i][w] !== best[i - 1][w]) {
      taken.unshift(i);
      w -= weight[i - 1];
    }
  }
  return taken;
}

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

pack(weight, fee, 6): best[i][w] е най-голямата такса с първите i колета и до w кг. Ред 0 е без колети, затова е само нули.
Остави колет i: най-доброто е каквото горният ред има за същите кг, best[i − 1][w]. Колет 1 тежи 4 кг, затова под 4 кг е само това.
Вземи колет i: таксата му плюс най-доброто на горния ред за останалите кг, best[i − 1][w − kg]. При 4 кг: 10 € + 0 = 10 € бие 0.
Ред 3, 6 кг: колет 3 (3 кг, 6 €) плюс най-доброто за 3 кг без него, 7 €: 13 € > 10 €. Два по-евтини колета бият най-скъпия на килограм.
Назад от долния десен ъгъл: същото като горе значи, че колетът е оставен, различно значи взет. Колет 4 не е взет, колет 3 е взет, колет 2 е взет, колет 1 не е взет: 2 + 3 = 13 €.

const weight = [4, 3, 3, 1];
const fee = [10, 7, 6, 2];
console.log(pack(weight, fee, 6));

[ 2, 3 ]

JavaScript няма двумерен масив: таблицата е масив от редове, всеки ред е отделен new Array(cap + 1).fill(0).

Идеята

Кои колети

Таблицата казва колко, а куриерът трябва да знае кои. Отговорът е в самата таблица. Тръгваш от долния десен ъгъл. Ако клетката е същата като горната, колет i не е нужен за нея: качваш се ред нагоре. Ако е различна, колет i е взет: качваш се ред нагоре и вървиш наляво с теглото му. Така до ред 0.

Днешните 20 колета и кутия от 50 кг:

function paid(fee, taken) {
  let sum = 0;
  for (const p of taken) {
    sum += fee[p - 1];
  }
  return sum;
}

const weight = [];
const fee = [];
for (let i = 0; i < 20; i++) {
  weight.push(1 + i * 7 % 20);
  fee.push(2 + i * 11 % 39);
}
const taken = pack(weight, fee, 50);
console.log(`${taken.join(" + ")}: ${paid(fee, taken)} €`);

1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €

Колетите тежат 48 кг и носят 208 €, най-много от всички над милион комбинации. Таблицата има 20 реда с колети по 51 клетки, общо 1020 клетки.

Пробвай

Попълни

Колет i влиза. Колко килограма остават за другите колети?

function pack(weight, fee, cap) {
  const n = weight.length;
  const best = [];
  for (let i = 0; i <= n; i++) {
    best.push(new Array(cap + 1).fill(0));
  }
  for (let i = 1; i <= n; i++) {
    const kg = weight[i - 1];
    const paid = fee[i - 1];
    for (let w = 0; w <= cap; w++) {
      best[i][w] = best[i - 1][w];
      if (kg <= w) {
        const take = best[i - 1][] + paid;
        best[i][w] = Math.max(best[i][w], take);
      }
    }
  }
  const taken = [];
  for (let i = n, w = cap; i > 0; i--) {
    if (best[i][w] !== best[i - 1][w]) {
      taken.unshift(i);
      w -= weight[i - 1];
    }
  }
  return taken;
}

Идеята

Защо не най-скъпото на килограм

Изглежда разумно: смяташ таксата на килограм за всеки колет и взимаш най-скъпия, който се събира, после следващия. В курса от 6 кг колет 1 е 2,50 € на килограм, колет 2 е около 2,33, колет 3 е 2, колет 4 е 2.

function greedy(weight, fee, cap) {
  const used = new Array(weight.length).fill(false);
  const taken = [];
  while (true) {
    let pick = -1;
    let rate = 0;
    for (let i = 0; i < weight.length; i++) {
      const perKg = fee[i] / weight[i];
      if (!used[i] && weight[i] <= cap && perKg > rate) {
        pick = i;
        rate = perKg;
      }
    }
    if (pick < 0) {
      return taken;
    }
    used[pick] = true;
    taken.push(pick + 1);
    cap -= weight[pick];
  }
}

const weight = [4, 3, 3, 1];
const fee = [10, 7, 6, 2];
const fast = greedy(weight, fee, 6);
const best = pack(weight, fee, 6);
console.log(`по €/кг: ${fast.join(" + ")} = ${paid(fee, fast)} €`);
console.log(`таблица: ${best.join(" + ")} = ${paid(fee, best)} €`);

по €/кг: 1 + 4 = 12 €
таблица: 2 + 3 = 13 €

Колет 1 влиза пръв и заема 4 кг. Остават 2 кг, и в тях влиза само колет 4. Колети 2 и 3 щяха да напълнят 6-те кг докрай и да носят повече. Правилото избира без да погледне назад, а първият му избор затваря по-добрата комбинация. Таблицата пробва и двете възможности за всеки колет и всяко място.

Ако колетите можеха да се режат (пясък, гориво), най-скъпото на килограм първо щеше да е вярно. Кога такова правило работи и кога лъже, е урокът „Кога алчният алгоритъм греши“.

Идеята

Един ред вместо таблица

Всеки ред чете само горния. Значи не трябва цялата таблица: стига един ред best[0..W], презаписван колет след колет. Когато само сумата е нужна, програмата става по-къса:

function bestFee(weight, fee, cap) {
  const best = new Array(cap + 1).fill(0);
  for (let i = 0; i < weight.length; i++) {
    for (let w = cap; w >= weight[i]; w--) {
      const take = best[w - weight[i]] + fee[i];
      best[w] = Math.max(best[w], take);
    }
  }
  return best[cap];
}

const weight = [4, 3, 3, 1];
const fee = [10, 7, 6, 2];
console.log(bestFee(weight, fee, 6), "€");

13 €

Важното е посоката: килограмите вървят отгоре надолу, от W към теглото на колета. Клетката w чете best[w − теглото], която е вляво от нея. Отгоре надолу тази клетка още не е презаписана в този кръг, значи е от горния ред, без текущия колет. Така колетът влиза най-много веднъж.

Пробвай

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

5 кг място и три колета: 2 кг за 3 €, 3 кг за 4 €, 4 кг за 5 €. Колко отпечатва програмата?

function bestFee(weight, fee, cap) {
  const best = new Array(cap + 1).fill(0);
  for (let i = 0; i < weight.length; i++) {
    for (let w = cap; w >= weight[i]; w--) {
      const take = best[w - weight[i]] + fee[i];
      best[w] = Math.max(best[w], take);
    }
  }
  return best[cap];
}

const weight = [2, 3, 4];
const fee = [3, 4, 5];
console.log(bestFee(weight, fee, 5), "€");

Отговор

8 €

5 €

7 €

Пробвай

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

Колега обърнал посоката на килограмите. За курса от 6 кг програмата му казва:

const weight = [4, 3, 3, 1];
const fee = [10, 7, 6, 2];
console.log(bestFee(weight, fee, 6), "€");

14 €

А най-доброто е 13 €. На кой ред е грешката?

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

Виж го

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

Броим проверените комбинации и сравненията „вземи или остави“ в реда. Кутията е 50 кг. Над 20 колета комбинациите не се пускат: те са точно 2ⁿ, затова оценката с „≈“ е точна.

Всички комбинации O(2ⁿ)
Таблица (до 50 кг) O(n)

Алгоритъм	n = 10	n = 20	n = 30	n = 40
Всички комбинации	1024	1 048 576	≈ 1 073 741 824	≈ 1 099 511 627 776
Таблица (до 50 кг)	425	810	1235	1620

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

function bestFee(weight, fee, cap) {
  const best = new Array(cap + 1).fill(0);
  for (let i = 0; i < weight.length; i++) {
    for (let w = cap; w >= weight[i]; w--) {
      const take = best[w - weight[i]] + fee[i];
      best[w] = Math.max(best[w], take);
    }
  }
  return best[cap];
}

Всеки нов колет удвоява комбинациите, а на таблицата добавя един ред: най-много 50 сравнения. При 40 колета таблицата прави 1620 сравнения, а комбинациите са над трилион. Затова и таблицата расте права: с постоянни 50 кг тя е O(n). Цената на W е в „По-точно“ долу.

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

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

let tries = 0;

function tryAll(weight, fee, cap, i, load, sum) {
  if (i === weight.length) {
    tries++;
    return load <= cap ? sum : -1;
  }
  const skip = tryAll(weight, fee, cap, i + 1, load, sum);
  const take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]);
  return Math.max(skip, take);
}

function bestFee(weight, fee, cap) {
  const best = new Array(cap + 1).fill(0);
  for (let i = 0; i < weight.length; i++) {
    for (let w = cap; w >= weight[i]; w--) {
      tries++;
      const take = best[w - weight[i]] + fee[i];
      best[w] = Math.max(best[w], take);
    }
  }
  return best[cap];
}

for (const n of [10, 20]) {
  const weight = [];
  const fee = [];
  for (let i = 0; i < n; i++) {
    weight.push(1 + i * 7 % 20);
    fee.push(2 + i * 11 % 39);
  }
  tries = 0;
  tryAll(weight, fee, 50, 0, 0, 0);
  const all = tries;
  tries = 0;
  bestFee(weight, fee, 50);
  console.log(`${n} колета: комбинации ${all}, таблица ${tries}`);
}

10 колета: комбинации 1024, таблица 425
20 колета: комбинации 1048576, таблица 810

Упражнение

Курсът от входа

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

Курс. Прочети товара в кг на първия ред, теглата на колетите на втория и таксите на третия. Отпечатай кои колети да вземе куриерът и колко изкарва. Ползвай pack и paid от урока.

15
5 6 3 4 7 2
11 14 6 9 15 3

1 + 2 + 4: 34 €

Още задачи

И колко кг. Отпечатай и колко тежат взетите колети, и колко място остава.
Спешни колети. Колет 2 трябва да тръгне непременно. Как ще го вкараш в задачата, без да пишеш нова таблица? (Подсказка: махни го от списъка и намали товара с теглото му.)
Две кутии. Велосипедът има две кутии по 25 кг. Защо не стига да решиш задачата за 50 кг?

По-точно

По-точно: цената на W

Защо „O(n · W)“ не значи „бързо винаги“.

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

Псевдополиномиално време. Таблицата има n · W клетки. n е колко колета има, но W е стойността на капацитета, а не колко неща има във входа. Ако теглата са в грамове, кутията от 50 кг става W = 50 000 и таблицата е хиляда пъти по-голяма. Ако капацитетът е милиард (байтове на диск, центове на бюджет), таблицата не се събира в паметта, а броят на колетите е същият. Време, което е полином в n и в стойността на W, но не в дължината на W в цифри, се нарича псевдополиномиално. Всяка цифра повече в W умножава работата по 10. Затова при огромни W и малко колети пробването на комбинации с добро рязане понякога е по-бързо.

Памет. Цялата таблица е (n + 1) · (W + 1) числа, един ред е W + 1. Но редът сам не казва кои колети: за връщането назад трябват всички редове, или поне по един бит „взет“ за всяка клетка.

Когато колетите са неограничени. Ако от всеки вид има колкото искаш (кашони с вода по 6 кг, всеки за 4 €), отгоре надолу вече е грешно, а отдолу нагоре е точно това, което трябва: всеки вид може да влезе пак. Това е същият цикъл като в рестото, където всяка монета може да се ползва много пъти. Грешката от „Намери грешката“ е вярното решение на друга задача.

Тест

Провери се

1. Какво значи клетката best[i][w] в таблицата на раницата?Таксата на колет i, ако тежи w кгКолко колета от първите i се събират в w кгНай-голямата такса, която се взима само от първите i колета, с товар до w кг

2. Клетката best[i][w] избира между две неща. Кои?Без колет i: best[i − 1][w]. С колет i: таксата му плюс best[i − 1][w − теглото му]Най-тежкият или най-скъпият колетКолет i или колет i − 1

3. Колетите са 4 кг за 10 €, 3 кг за 7 €, 3 кг за 6 € и 1 кг за 2 €, а мястото е 6 кг. Какво взима правилото „най-скъпото на килограм, което още се събира“?Колети 1 и 4, 12 €, а най-доброто е колети 2 и 3, 13 €Колети 2 и 3, 13 €, най-добротоСамо колет 1, 10 €

4. В таблицата с един ред капацитетът върви отгоре надолу. Какво става, ако върви отдолу нагоре?Нищо, отговорът е същиятПрограмата чете извън масиваbest[w − теглото] вече може да съдържа същия колет, и той влиза два пъти

5. Таблицата е O(n · W). Защо това не е „бързо винаги“?Защото n · W винаги е повече от 2ⁿЗащото таблицата се пълни два пътиW е числото на капацитета, а не броят на нещата. С грамове вместо килограми таблицата става хиляда пъти по-голяма

Задачата за раницата

Бисквитки