Задачата за раницата
Накратко: Задачата за раницата избира предмети с най-голяма обща стойност, без да мине дадено тегло; таблицата „предмети × тегло“ на динамичното програмиране я решава за O(n · W).
Проблем
Кои колети в кутията
Куриер кара товарен велосипед, а кутията му носи до 50 кг. В склада го чакат колети. Всеки има тегло и такса за доставка, а куриерът получава таксата за всеки доставен колет. Колет не се разделя: взима се цял или изобщо не се взима. Кои колети да вземе, за да изкара най-много?
Програмистът пробва всичко: за всеки колет „взимам“ или „не взимам“. Когато е решил за всички, проверява дали товарът се събира и колко носи. Колетите идват от склада. Тук ги строим с формула, за да са едни и същи на всеки език: тегло от 1 до 20 кг, такса от 2 до 40 €.
static long tries = 0;
static int TryAll(int[] weight, int[] fee, int cap, int i, int load, int sum){ if (i == weight.Length) { tries++; return load <= cap ? sum : -1; } int skip = TryAll(weight, fee, cap, i + 1, load, sum); int take = TryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]); return Math.Max(skip, take);}
foreach (int n in new[] { 10, 20 }){ int[] weight = new int[n]; int[] fee = new int[n]; for (int i = 0; i < n; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39; } tries = 0; int best = TryAll(weight, fee, 50, 0, 0, 0); Console.WriteLine($"{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 кг място и чакат четири колета. Гледай двете клетки, които всяка клетка чете: горната („остави“) и стрелката от горния ред с таксата („вземи“):
static List<int> Pack(int[] weight, int[] fee, int cap){ int n = weight.Length; int[,] best = new int[n + 1, cap + 1]; for (int i = 1; i <= n; i++) { int kg = weight[i - 1]; int paid = fee[i - 1]; for (int w = 0; w <= cap; w++) { best[i, w] = best[i - 1, w]; if (kg <= w) { int take = best[i - 1, w - kg] + paid; best[i, w] = Math.Max(best[i, w], take); } } } List<int> taken = new List<int>(); for (int i = n, w = cap; i > 0; i--) { if (best[i, w] != best[i - 1, w]) { taken.Insert(0, 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 €.
int[] weight = { 4, 3, 3, 1 };int[] fee = { 10, 7, 6, 2 };Console.WriteLine(string.Join(" + ", Pack(weight, fee, 6)));2 + 3int[,], а клетката се пише best[i, w], с два индекса в едни скоби.Идеята
Кои колети
Таблицата казва колко, а куриерът трябва да знае кои. Отговорът е в самата таблица. Тръгваш от долния десен ъгъл. Ако клетката е същата като горната, колет i не е нужен за нея: качваш се ред нагоре. Ако е различна, колет i е взет: качваш се ред нагоре и вървиш наляво с теглото му. Така до ред 0.
Днешните 20 колета и кутия от 50 кг:
static int Paid(int[] fee, List<int> taken){ int sum = 0; foreach (int p in taken) { sum += fee[p - 1]; } return sum;}
int[] weight = new int[20];int[] fee = new int[20];for (int i = 0; i < 20; i++){ weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39;}List<int> taken = Pack(weight, fee, 50);Console.WriteLine($"{string.Join(" + ", taken)}: {Paid(fee, taken)} €");1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €Колетите тежат 48 кг и носят 208 €, най-много от всички над милион комбинации. Таблицата има 20 реда с колети по 51 клетки, общо 1020 клетки.
Пробвай
Попълни
Колет i влиза. Колко килограма остават за другите колети?
static List<int> Pack(int[] weight, int[] fee, int cap)
{
int n = weight.Length;
int[,] best = new int[n + 1, cap + 1];
for (int i = 1; i <= n; i++)
{
int kg = weight[i - 1];
int paid = fee[i - 1];
for (int w = 0; w <= cap; w++)
{
best[i, w] = best[i - 1, w];
if (kg <= w)
{
int take = best[i - 1, ] + paid;
best[i, w] = Math.Max(best[i, w], take);
}
}
}
List<int> taken = new List<int>();
for (int i = n, w = cap; i > 0; i--)
{
if (best[i, w] != best[i - 1, w])
{
taken.Insert(0, i);
w -= weight[i - 1];
}
}
return taken;
}Колетът заема kg от w килограма, остават w - kg. Най-доброто за тях без колет i е в горния ред, в колоната w - kg, и вече е готово.
Идеята
Защо не най-скъпото на килограм
Изглежда разумно: смяташ таксата на килограм за всеки колет и взимаш най-скъпия, който се събира, после следващия. В курса от 6 кг колет 1 е 2,50 € на килограм, колет 2 е около 2,33, колет 3 е 2, колет 4 е 2.
static List<int> Greedy(int[] weight, int[] fee, int cap){ bool[] used = new bool[weight.Length]; List<int> taken = new List<int>(); while (true) { int pick = -1; double rate = 0; for (int i = 0; i < weight.Length; i++) { double perKg = (double)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.Add(pick + 1); cap -= weight[pick]; }}int[] weight = { 4, 3, 3, 1 };int[] fee = { 10, 7, 6, 2 };List<int> fast = Greedy(weight, fee, 6);List<int> best = Pack(weight, fee, 6);Console.WriteLine($"по €/кг: {string.Join(" + ", fast)} = {Paid(fee, fast)} €");Console.WriteLine($"таблица: {string.Join(" + ", best)} = {Paid(fee, best)} €");по €/кг: 1 + 4 = 12 €таблица: 2 + 3 = 13 €Колет 1 влиза пръв и заема 4 кг. Остават 2 кг, и в тях влиза само колет 4. Колети 2 и 3 щяха да напълнят 6-те кг докрай и да носят повече. Правилото избира без да погледне назад, а първият му избор затваря по-добрата комбинация. Таблицата пробва и двете възможности за всеки колет и всяко място.
Ако колетите можеха да се режат (пясък, гориво), най-скъпото на килограм първо щеше да е вярно. Кога такова правило работи и кога лъже, е урокът „Кога алчният алгоритъм греши“.
Идеята
Един ред вместо таблица
Всеки ред чете само горния. Значи не трябва цялата таблица: стига един ред best[0..W], презаписван колет след колет. Когато само сумата е нужна, програмата става по-къса:
static int BestFee(int[] weight, int[] fee, int cap){ int[] best = new int[cap + 1]; for (int i = 0; i < weight.Length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.Max(best[w], take); } } return best[cap];}int[] weight = { 4, 3, 3, 1 };int[] fee = { 10, 7, 6, 2 };Console.WriteLine(BestFee(weight, fee, 6) + " €");13 €Важното е посоката: килограмите вървят отгоре надолу, от W към теглото на колета. Клетката w чете best[w − теглото], която е вляво от нея. Отгоре надолу тази клетка още не е презаписана в този кръг, значи е от горния ред, без текущия колет. Така колетът влиза най-много веднъж.
Пробвай
Предвиди изхода
5 кг място и три колета: 2 кг за 3 €, 3 кг за 4 €, 4 кг за 5 €. Колко отпечатва програмата?
static int BestFee(int[] weight, int[] fee, int cap){ int[] best = new int[cap + 1]; for (int i = 0; i < weight.Length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.Max(best[w], take); } } return best[cap];}
int[] weight = { 2, 3, 4 };int[] fee = { 3, 4, 5 };Console.WriteLine(BestFee(weight, fee, 5) + " €");Колети 1 и 2 тежат точно 5 кг и носят 7 €. Колет 3 е най-скъпият, но сам носи 5 €, а с колет 1 стават 6 кг и не се събират. 8 € е тъкмо тази невъзможна двойка.
Пробвай
Намери грешката
Колега обърнал посоката на килограмите. За курса от 6 кг програмата му казва:
int[] weight = { 4, 3, 3, 1 };int[] fee = { 10, 7, 6, 2 };Console.WriteLine(BestFee(weight, fee, 6) + " €");14 €А най-доброто е 13 €. На кой ред е грешката?
Избери реда с грешката.
Килограмите вървят отдолу нагоре. Когато клетката w чете best[w − теглото], тя вече е презаписана в същия кръг, с този колет вътре. Така колет 2 (3 кг, 7 €) влиза в 3 кг, а после пак в 6 кг: 7 + 7 = 14 €. Отгоре надолу клетката отляво е още от предишния кръг и всеки колет влиза най-много веднъж.
Виж го
Измери го: всички комбинации срещу таблицата
Броим проверените комбинации и сравненията „вземи или остави“ в реда. Кутията е 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 |
static int BestFee(int[] weight, int[] fee, int cap){ int[] best = new int[cap + 1]; for (int i = 0; i < weight.Length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.Max(best[w], take); } } return best[cap];}Всеки нов колет удвоява комбинациите, а на таблицата добавя един ред: най-много 50 сравнения. При 40 колета таблицата прави 1620 сравнения, а комбинациите са над трилион. Затова и таблицата расте права: с постоянни 50 кг тя е O(n). Цената на W е в „По-точно“ долу.
По-точно, за любопитните
Същите числа на твоя език:
static long tries = 0;
static int TryAll(int[] weight, int[] fee, int cap, int i, int load, int sum){ if (i == weight.Length) { tries++; return load <= cap ? sum : -1; } int skip = TryAll(weight, fee, cap, i + 1, load, sum); int take = TryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]); return Math.Max(skip, take);}
static int BestFee(int[] weight, int[] fee, int cap){ int[] best = new int[cap + 1]; for (int i = 0; i < weight.Length; i++) { for (int w = cap; w >= weight[i]; w--) { tries++; int take = best[w - weight[i]] + fee[i]; best[w] = Math.Max(best[w], take); } } return best[cap];}
foreach (int n in new[] { 10, 20 }){ int[] weight = new int[n]; int[] fee = new int[n]; for (int i = 0; i < n; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39; } tries = 0; TryAll(weight, fee, 50, 0, 0, 0); long all = tries; tries = 0; BestFee(weight, fee, 50); Console.WriteLine($"{n} колета: комбинации {all}, таблица {tries}");}10 колета: комбинации 1024, таблица 42520 колета: комбинации 1048576, таблица 810Упражнение
Курсът от входа
Реши задачата в редактора си.
Курс. Прочети товара в кг на първия ред, теглата на колетите на втория и таксите на третия. Отпечатай кои колети да вземе куриерът и колко изкарва. Ползвай Pack и Paid от урока.
155 6 3 4 7 211 14 6 9 15 31 + 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 €), отгоре надолу вече е грешно, а отдолу нагоре е точно това, което трябва: всеки вид може да влезе пак. Това е същият цикъл като в рестото, където всяка монета може да се ползва много пъти. Грешката от „Намери грешката“ е вярното решение на друга задача.
Тест