Задачата за раницата
Накратко: Задачата за раницата избира предмети с най-голяма обща стойност, без да мине дадено тегло; таблицата „предмети × тегло“ на динамичното програмиране я решава за O(n · W).
Проблем
Кои колети в кутията
Куриер кара товарен велосипед, а кутията му носи до 50 кг. В склада го чакат колети. Всеки има тегло и такса за доставка, а куриерът получава таксата за всеки доставен колет. Колет не се разделя: взима се цял или изобщо не се взима. Кои колети да вземе, за да изкара най-много?
Програмистът пробва всичко: за всеки колет „взимам“ или „не взимам“. Когато е решил за всички, проверява дали товарът се събира и колко носи. Колетите идват от склада. Тук ги строим с формула, за да са едни и същи на всеки език: тегло от 1 до 20 кг, такса от 2 до 40 €.
tries = 0
def try_all(weight, fee, cap, i, load, total): global tries if i == len(weight): tries += 1 return total if load <= cap else -1 skip = try_all(weight, fee, cap, i + 1, load, total) take = try_all(weight, fee, cap, i + 1, load + weight[i], total + fee[i]) return max(skip, take)
for n in [10, 20]: weight = [] fee = [] for i in range(n): weight.append(1 + i * 7 % 20) fee.append(2 + i * 11 % 39) tries = 0 best = try_all(weight, fee, 50, 0, 0, 0) print(f"{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 кг място и чакат четири колета. Гледай двете клетки, които всяка клетка чете: горната („остави“) и стрелката от горния ред с таксата („вземи“):
def pack(weight, fee, cap): n = len(weight) best = [[0] * (cap + 1) for _ in range(n + 1)] for i in range(1, n + 1): kg = weight[i - 1] paid = fee[i - 1] for w in range(cap + 1): best[i][w] = best[i - 1][w] if kg <= w: take = best[i - 1][w - kg] + paid best[i][w] = max(best[i][w], take) taken = [] w = cap for i in range(n, 0, -1): 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 €.
weight = [4, 3, 3, 1]fee = [10, 7, 6, 2]print(pack(weight, fee, 6))[2, 3][[0] * (cap + 1) for _ in range(n + 1)] прави n + 1 отделни реда. [[0] * (cap + 1)] * (n + 1) би сложил един и същ ред n + 1 пъти, и запис в един ред би сменил всички.Идеята
Кои колети
Таблицата казва колко, а куриерът трябва да знае кои. Отговорът е в самата таблица. Тръгваш от долния десен ъгъл. Ако клетката е същата като горната, колет i не е нужен за нея: качваш се ред нагоре. Ако е различна, колет i е взет: качваш се ред нагоре и вървиш наляво с теглото му. Така до ред 0.
Днешните 20 колета и кутия от 50 кг:
def paid(fee, taken): total = 0 for p in taken: total += fee[p - 1] return total
weight = []fee = []for i in range(20): weight.append(1 + i * 7 % 20) fee.append(2 + i * 11 % 39)taken = pack(weight, fee, 50)print(f"{" + ".join(map(str, taken))}: {paid(fee, taken)} €")1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €Колетите тежат 48 кг и носят 208 €, най-много от всички над милион комбинации. Таблицата има 20 реда с колети по 51 клетки, общо 1020 клетки.
Пробвай
Попълни
Колет i влиза. Колко килограма остават за другите колети?
def pack(weight, fee, cap):
n = len(weight)
best = [[0] * (cap + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
kg = weight[i - 1]
paid = fee[i - 1]
for w in range(cap + 1):
best[i][w] = best[i - 1][w]
if kg <= w:
take = best[i - 1][] + paid
best[i][w] = max(best[i][w], take)
taken = []
w = cap
for i in range(n, 0, -1):
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.
def greedy(weight, fee, cap): used = [False] * len(weight) taken = [] while True: pick = -1 rate = 0 for i in range(len(weight)): per_kg = fee[i] / weight[i] if not used[i] and weight[i] <= cap and per_kg > rate: pick = i rate = per_kg if pick < 0: return taken used[pick] = True taken.append(pick + 1) cap -= weight[pick]weight = [4, 3, 3, 1]fee = [10, 7, 6, 2]fast = greedy(weight, fee, 6)best = pack(weight, fee, 6)print(f"по €/кг: {" + ".join(map(str, fast))} = {paid(fee, fast)} €")print(f"таблица: {" + ".join(map(str, best))} = {paid(fee, best)} €")по €/кг: 1 + 4 = 12 €таблица: 2 + 3 = 13 €Колет 1 влиза пръв и заема 4 кг. Остават 2 кг, и в тях влиза само колет 4. Колети 2 и 3 щяха да напълнят 6-те кг докрай и да носят повече. Правилото избира без да погледне назад, а първият му избор затваря по-добрата комбинация. Таблицата пробва и двете възможности за всеки колет и всяко място.
Ако колетите можеха да се режат (пясък, гориво), най-скъпото на килограм първо щеше да е вярно. Кога такова правило работи и кога лъже, е урокът „Кога алчният алгоритъм греши“.
Идеята
Един ред вместо таблица
Всеки ред чете само горния. Значи не трябва цялата таблица: стига един ред best[0..W], презаписван колет след колет. Когато само сумата е нужна, програмата става по-къса:
def best_fee(weight, fee, cap): best = [0] * (cap + 1) for i in range(len(weight)): for w in range(cap, weight[i] - 1, -1): take = best[w - weight[i]] + fee[i] best[w] = max(best[w], take) return best[cap]weight = [4, 3, 3, 1]fee = [10, 7, 6, 2]print(best_fee(weight, fee, 6), "€")13 €Важното е посоката: килограмите вървят отгоре надолу, от W към теглото на колета. Клетката w чете best[w − теглото], която е вляво от нея. Отгоре надолу тази клетка още не е презаписана в този кръг, значи е от горния ред, без текущия колет. Така колетът влиза най-много веднъж.
Пробвай
Предвиди изхода
5 кг място и три колета: 2 кг за 3 €, 3 кг за 4 €, 4 кг за 5 €. Колко отпечатва програмата?
def best_fee(weight, fee, cap): best = [0] * (cap + 1) for i in range(len(weight)): for w in range(cap, weight[i] - 1, -1): take = best[w - weight[i]] + fee[i] best[w] = max(best[w], take) return best[cap]
weight = [2, 3, 4]fee = [3, 4, 5]print(best_fee(weight, fee, 5), "€")Колети 1 и 2 тежат точно 5 кг и носят 7 €. Колет 3 е най-скъпият, но сам носи 5 €, а с колет 1 стават 6 кг и не се събират. 8 € е тъкмо тази невъзможна двойка.
Пробвай
Намери грешката
Колега обърнал посоката на килограмите. За курса от 6 кг програмата му казва:
weight = [4, 3, 3, 1]fee = [10, 7, 6, 2]print(best_fee(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 |
def best_fee(weight, fee, cap): best = [0] * (cap + 1) for i in range(len(weight)): for w in range(cap, weight[i] - 1, -1): take = best[w - weight[i]] + fee[i] best[w] = max(best[w], take) return best[cap]Всеки нов колет удвоява комбинациите, а на таблицата добавя един ред: най-много 50 сравнения. При 40 колета таблицата прави 1620 сравнения, а комбинациите са над трилион. Затова и таблицата расте права: с постоянни 50 кг тя е O(n). Цената на W е в „По-точно“ долу.
По-точно, за любопитните
Същите числа на твоя език:
tries = 0
def try_all(weight, fee, cap, i, load, total): global tries if i == len(weight): tries += 1 return total if load <= cap else -1 skip = try_all(weight, fee, cap, i + 1, load, total) take = try_all(weight, fee, cap, i + 1, load + weight[i], total + fee[i]) return max(skip, take)
def best_fee(weight, fee, cap): global tries best = [0] * (cap + 1) for i in range(len(weight)): for w in range(cap, weight[i] - 1, -1): tries += 1 take = best[w - weight[i]] + fee[i] best[w] = max(best[w], take) return best[cap]
for n in [10, 20]: weight = [] fee = [] for i in range(n): weight.append(1 + i * 7 % 20) fee.append(2 + i * 11 % 39) tries = 0 try_all(weight, fee, 50, 0, 0, 0) every = tries tries = 0 best_fee(weight, fee, 50) print(f"{n} колета: комбинации {every}, таблица {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 €), отгоре надолу вече е грешно, а отдолу нагоре е точно това, което трябва: всеки вид може да влезе пак. Това е същият цикъл като в рестото, където всяка монета може да се ползва много пъти. Грешката от „Намери грешката“ е вярното решение на друга задача.
Тест