L7.1 Kapitola K7 — Knapsack (doplňková) · [MUST]

Knapsack DP (tabulka + backtracking)

Jedna nová věc DP tabulka pro 0/1 batoh indexovaná položkami × kapacitou: buňka $F(j, W')$ = nejlepší cena z položek $1..j$ při kapacitě $W'$, vyplnění v $O(nW)$ a backtracking (zpětný průchod), který z hotové tabulky vyčte vybrané položky i (ne)unikátnost optima.

Batoh už znáš: definici, Dantzigův greedy pro frakční variantu i 2-aproximaci jsi viděl v [L3.11] Fractional knapsack a 2-aproximace, a v [L3.5] Silná NP-těžkost padlo, že batoh má pseudopolynomiální DP. Dnes to DP konečně postavíme a propočítáme — přesně v podobě, kterou chce zkouška (doložené zadání 2023 i 09.07.2021, propočítáš v T01). Připomenutí zadání problému (slide 3, EN 1:1):

Knapsack problem (slide 3, EN 1:1)

Instance: Nonnegative integers $n, c_1, \ldots, c_n, w_1, \ldots, w_n, W$ […] Goal: Find a subset $S \subseteq \{1, \ldots, n\}$ such that $\sum_{j \in S} w_j \le W$ and $\sum_{j \in S} c_j$ is the maximum.

Stav: co si stačí pamatovat

Rozhoduj o položkách postupně: nejdřív o $I_1$, pak o $I_2$, … U každé jsou jen dvě možnosti — vzít / nevzít (binární rozhodnutí jako $x_j \in \{0,1\}$ v [L0.8] Binární proměnná). Naivně je to strom $2^n$ větví.

Zkus sám: rozhodl jsi o položkách $1..j$ (nějak). Co jediné z té historie potřebuje zbytek úlohy (rozhodování o $j{+}1..n$) znát, aby mohl pokračovat optimálně?

Jen kolik kapacity zbývá. Zbytek úlohy „maximalizuj cenu z položek $j{+}1..n$ do zbylé kapacity“ vůbec nezajímá, které z položek $1..j$ jsi vzal — dvě různé historie se stejnou zbylou kapacitou mají identickou budoucnost. Stav tedy je dvojice $(j, W')$: uvažovány položky $1..j$, k dispozici kapacita $W'$. Stavů je jen $(n+1)(W+1)$ místo $2^n$ větví — dvě větve stromu, které se potkají ve stejném stavu, stačí počítat jednou a nechat si tu lepší. Slide 10 tomu říká diamonds (kosočtverce ve stavovém prostoru) a vlastnosti optimal substructure + overlapping subproblems; lepší řešení v každém stavu vybíráme díky Bellman's Principle of Optimality.

Definuj tedy (kapacitně indexovaná tabulka; oproti vzorovému řešení banky prohazujeme pořadí argumentů na $(j, W')$, aby řádky odpovídaly položkám):

$$F(j, W') = \text{nejlepší dosažitelná cena výběru z položek } 1, \ldots, j \text{ s váhou} \le W'.$$

Rekurence: vzít × nevzít

Buňku $F(j, W')$ spočteš porovnáním obou rozhodnutí o položce $j$:

$$F(j, W') = \begin{cases} F(j-1,\, W'), & w_j > W' \quad (\text{nevejde se}),\\[2pt] \max\bigl\{\underbrace{F(j-1,\, W')}_{\text{nevzít}},\ \underbrace{F(j-1,\, W' - w_j) + c_j}_{\text{vzít}}\bigr\}, & w_j \le W', \end{cases}$$

se základem $F(0, W') = 0$ (bez položek je cena 0) a $F(j, 0) = 0$.

Zkus sám: proč se ve větvi „vzít“ čte $F(j-1,\, W'-w_j)$, tedy řádek $j-1$ — a ne $F(j,\, W'-w_j)$ ze stejného řádku $j$?

Protože řešíme 0/1 knapsack: položku $j$ smíš vzít nejvýš jednou. Jakmile ji vezmeš, o zbytek kapacity se smí ucházet už jen položky $1..j{-}1$. Kdybys četl řádek $j$, mohla by se položka $j$ „vzít“ opakovaně — to je rekurence pro unbounded (neomezený) batoh: $F(j,W') = \max\{F(j{-}1,W'),\ F(j,W'-w_j)+c_j\}$. Rozdíl jediného indexu úplně mění úlohu (vzorové řešení banky to explicitně zdůrazňuje) — a u zkouškové instance by dal jiný výsledek, viz T01.

Pozor na orientaci: přednáška vs. zkouškové řešení

Slidy 8–9 předvádějí DP pro batoh primárně indexované cenou ($x_k^j$ = minimální váha, kterou lze dosáhnout ceny $k$ z položek $1..j$, složitost $O(nC)$) — to je varianta příští lekce [L7.2] a základ aproximačního schématu. Slide 10 ale dodává (EN 1:1): “If the weights are integers, we can solve the problem by dynamic programming while selecting the solution having the higher cost for given weight.” Přesně tuhle váhovou (kapacitní) tabulku používá vzorové řešení banky i ruční zkoušková řešení — váhy v zadáních jsou malá celá čísla, kdežto ceny mohou být i necelé (slide 10 schválně volí $c = (3.1,\, 4.2,\, 5.1,\, 4.3)$). Dnešní lekce = kapacitní tabulka.

Tabulka a její vyplnění

Tabulka má řádky $j = 0..n$ a sloupce $W' = 0..W$; vyplňuje se po řádcích (řádek $j$ čte jen řádek $j-1$). Projdi si to na příkladu ze slidu 10 (blackboard example, integer weights): $n = 4$, $w = (2, 3, 4, 5)$, $c = (3.1,\, 4.2,\, 5.1,\, 4.3)$, $W = 8$ — instance je ze slidu, samotné vyplnění a krokování je naše. Nejdřív ale:

Zkus sám: řádek $I_1$ ($c=3.1$, $w=2$) má hodnoty $0, 0, 3.1, 3.1, \ldots, 3.1$. Vyplň z něj řádek $I_2$ ($c=4.2$, $w=3$) pro $W' = 0..8$, než si to pustíš ve steperu.

$W' \in \{0,1\}$: nevejde se ani jedna → $0, 0$. $W'=2$: $I_2$ se nevejde → opiš $3.1$. $W'=3$: $\max\{3.1,\ F(1,0)+4.2\} = \max\{3.1, 4.2\} = 4.2$. $W'=4$: $\max\{3.1,\ F(1,1)+4.2\} = 4.2$. $W'=5..8$: $\max\{3.1,\ 3.1+4.2\} = 7.3$ (obě položky najednou). Celý řádek: $0, 0, 3.1, 4.2, 4.2, 7.3, 7.3, 7.3, 7.3$.

Backtracking: z čísel zpět k položkám

Zkus sám: tabulka ti dala jediné číslo — optimum $9.3$. Zadání ale chce items in knapsack. Jak z hotové tabulky poznáš, jestli byla položka $j$ v optimu vzata?

Zopakuj v buňce rozhodnutí, kterým vznikla: stojíš-li na $(j, W')$ a $F(j, W') = F(j-1, W')$, mohla být položka $j$ nevzata — posuň se o řádek výš beze změny sloupce. Pokud se hodnoty liší, muselo platit „vzít“: $F(j, W') = F(j-1, W'-w_j) + c_j$ — položka $j$ je v řešení a skočíš na $(j-1,\, W'-w_j)$. Start v pravém dolním rohu $(n, W)$, konec v řádku $0$. (Přednáškový pseudokód si k tomu ukládá bit $s_k^j$, „which of the two possible cases has happened — it is later used to reconstruct the selection“; s tabulkou před sebou ho ale zrekonstruuješ i bez ukládání.)

Pokračuj ve steperu výše: kroky 6–9 předvádějí zpětný průchod — výsledek $S = \{I_2, I_3\}$, cena $4.2 + 5.1 = 9.3$, váha $3 + 4 = 7 \le 8$.

Zkus sám: zkouška se pravidelně ptá „Is this solution unique and why?“ (tj. existuje více optimálních řešení? — opakuje to i studentský souhrn). Kdy z tabulky poznáš, že optim je víc?

Každé optimální řešení odpovídá nějaké zpětné cestě tabulkou. Optimum není jediné, právě když se při backtrackingu v některé buňce na optimální cestě obě volby remizují: $F(j-1, W') = F(j-1, W'-w_j) + c_j = F(j,W')$ — cesta se větví a každá větev dá jiný výběr položek (jedna s $I_j$, druhá bez). Je-li v každé buňce cesty rozhodnutí jednoznačné (žádná remíza), je cesta jediná a optimum unikátní. V příkladu ze slidu: na $(4,8)$ dává „vzít“ jen $F(3,3)+4.3 = 8.5 \ne 9.3$, na $(3,8)$ dává „nevzít“ jen $7.3$, na $(2,4)$ „nevzít“ $3.1$, na $(1,1)$ „vzít“ se nevejde — vše jednoznačné, $\{I_2, I_3\}$ je unikátní. Pozor: argument musíš projít po celé cestě, ne jen v rohu (propočítáš si to na remíze v T02).

Složitost: $O(nW)$ — a co je to za třídu?

Zkus sám: vyplnění stojí $O(nW)$ — konstantní práce na buňku, $(n+1)(W+1)$ buněk; backtracking jen $O(n)$ kroků. Batoh je přitom NP-těžký. Je $O(nW)$ polynomiální algoritmus? A co se změní, když zadání slíbí $W \le 10n$?

Není — $W$ je ve vstupu zapsáno binárně na $O(\log W)$ bitů, takže $O(nW)$ je exponenciální v délce vstupu: pseudopolynomiální algoritmus, přesně jak rozebírá [L3.5] (batoh proto není silně NP-těžký). Když ale zadání omezí $W \le 10n$, dostaneš $O(nW) \le O(n \cdot 10n) = O(n^2)$ — na téhle třídě instancí běží DP polynomiálně v $n$. To je doslova otázka b) zkouškové úlohy (T01). Bonus ze vzorového řešení: paměť jde srazit na $O(W)$, protože řádek $j$ čte jen řádek $j-1$.

Pozor: za co se u téhle úlohy ztrácí body

Mimochodem, stejnou DP techniku „stav = dosažitelné hodnoty, rekurence vzít/nevzít“ už jsi potkal u Rothkopfa [L5.11] (stav = zátěže strojů) — a princip „kombinuj optima podproblémů“ i u Floyda [L2.14].

Key takeaways — L7.1
T01 Knapsack — DP tabulka + backtracking zdroj: zkouška 2023 (str. 4, úloha 6b) = zkouška 09.07.2021 = task bank #27, zadání 1:1
Assignment (original, EN)

“Using dynamic programming, solve the following instance of Knapsack Problem:

  • number of items: $n = 7$
  • knapsack capacity: $W = 5$
  • costs $\mathbf{c} = (2, 2, 2, 2, 4, 3, 1)$
  • weights $\mathbf{w} = (1, 1, 2, 2, 3, 4, 1)$

a) Compute the optimal solution (objective value and items in knapsack) of this instance of Knapsack Problem. Write down all iterations of the algorithm. Is this solution unique and why?

b) What can you say about the computational complexity of the algorithm for instances where $W \le 10n$?”

a) Co je v zadání?

Konkrétní instance 0/1 batohu: 7 položek, kapacita 5, ceny a váhy dané vektory. Chce se: vyřešit dynamickým programováním, vypsat všechny iterace (= celou tabulku), uvést optimální cenu a vybrané položky, rozhodnout unikátnost se zdůvodněním; v části b) složitost na třídě instancí s $W \le 10n$.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Tabulka 8 řádků ($j = 0..7$) × 6 sloupců ($W' = 0..5$), vyplňuj po řádcích rekurencí; všimni si, že položky $I_1, I_2$ jsou identické ($c=2$, $w=1$) a stejně tak $I_3, I_4$ ($c=2$, $w=2$). Pak backtracking z $(7, 5)$: u každé buňky rozhodni vzít/nevzít a hlídej remízy (kvůli otázce unikátnosti). Pro b) dosaď omezení $W \le 10n$ do $O(nW)$. Nejdřív celé na papír, pak teprve krokuj řešení níže.

d) Úplné řešení

a) Všechny iterace (krokuj — vyplnění řádků $I_1..I_7$ = iterace algoritmu, pak zpětný průchod):

Optimální cena $F(7,5) = \mathbf{8}$. Backtracking (kroky 9–14 výše): $I_7$ ne, $I_6$ ne, $\mathbf{I_5}$ ano (skok na $W'=2$), $I_4$ ne, $I_3$ ne, $\mathbf{I_2}$ ano (skok na $W'=1$), $\mathbf{I_1}$ ano (skok na $W'=0$, konec). Tedy

$$S = \{I_1, I_2, I_5\}, \qquad w_1+w_2+w_5 = 1+1+3 = 5 \le 5, \qquad c_1+c_2+c_5 = 2+2+4 = \mathbf{8}.$$

Unikátnost: ANO. V žádné buňce zpětné cesty nenastala remíza — např. v $(7,5)$ dává „vzít $I_7$“ jen $F(6,4)+1 = 7 \ne 8$, v $(6,5)$ dává „vzít $I_6$“ jen $F(5,1)+3 = 5$, v $(5,5)$ dává „nevzít“ jen $6$ — takže tabulkou vede jediná optimální cesta (přesně argument ručního zkouškového řešení: „existuje jen jedna cesta … do optima“). Kombinatorická kontrola: hodnotu 8 dává i více podmnožin (např. libovolné dvě z $I_1..I_4$ plus $I_5$ = $2+2+4$, dále $2+2+2+2 = \{I_1..I_4\}$ či $4+3+1 = \{I_5,I_6,I_7\}$), ale všechny kromě $\{I_1,I_2,I_5\}$ (váha 5 ✓) mají váhu > 5 — projde jediná množina. (Identické dvojice $I_1{=}I_2$ a $I_3{=}I_4$ tu alternativu nevyrobí: obě položky první dvojice v řešení jsou, druhá dvojice v něm není celá.)

b) Tabulka má $(n+1)(W+1)$ buněk, konstantní práce na buňku: čas i paměť $O(nW)$, paměť lze srazit na $O(W)$. Obecně je to pseudopolynomiální algoritmus [L3.5]; na instancích s $W \le 10n$ ale $O(nW) \le O(n \cdot 10n) = O(n^2)$ — algoritmus je na této třídě polynomiální v počtu položek $n$.

Poznámky ke zdrojům (přiznáno): ① Ruční tabulka zkoušky 2023 je s naší identická (řádky $I_1..I_7$, poslední řádek $0,2,4,5,6,8$, hodnota 8 zakroužkovaná jako „maximální cena“) a množina $\{I_1, I_2, I_5\}$ souhlasí; přepis ale u závěru uvádí „$c_{opt} = 6$“ — to odporuje vlastní tabulce i součtu $2+2+4=8$ a řešení banky #27 (= 8), počítáme tedy 8. ② Červená poznámka hodnotitele u unikátnosti (přepis, přibližně): „Když zde nepíšete kombinatorické řešení, je možné uvést, že opt. řešení nemusí být v pravém dolním rohu.“ — u kapacitní tabulky v rohu optimum vždy je (monotonie po řádcích i sloupcích); výhrada míří na obecné DP z přednášky indexované cenou [L7.2], kde optimum = nejvyšší dosažitelná cena $k$ s $x_k^n \le W$, nikoli roh. ③ Drill z poznámky banky: v unbounded variantě (větev „vzít“ čte řádek $j$) by optimum bylo $5 \cdot 2 = 10$ — pětkrát položka $I_1$ — a unikátní by nebylo ($I_2$ je identická).

T02 Více optimálních řešení — remíza v tabulce vlastní drill (přiznáno) po vzoru otázky „Is this solution unique?“ / souhrnu „existuje více optimálních řešení?“
Assignment (vlastní, EN ve stylu zkoušky)

“Using dynamic programming, solve the following instance of Knapsack Problem: $n = 3$, $W = 2$, costs $\mathbf{c} = (3, 2, 1)$, weights $\mathbf{w} = (2, 1, 1)$. Compute the optimal solution, write down all iterations, and decide: is the solution unique and why?”

a) Co je v zadání?

Miniaturní instance (tabulka 4×3) zvolená tak, aby otázka unikátnosti dopadla opačně než v T01 — trénink na rozpoznání remízy.

b) Co k tomu budeme potřebovat?

  • Tato lekce — zejména kritérium unikátnosti (remíza na zpětné cestě).

c) Jak nad úlohou uvažovat?

Vyplň tři řádky tabulky a spusť backtracking z $(3, 2)$. V první buňce porovnej obě hodnoty z rekurence — nespokoj se s první volbou, která „sedí“.

d) Úplné řešení

Optimum $F(3,2) = 3$. Backtracking z $(3,2)$: remíza — „nevzít $I_3$“ dává $F(2,2) = 3$ a „vzít $I_3$“ dává $F(2,1) + 1 = 2 + 1 = 3$ též. Cesta se větví:

  • Větev „nevzít $I_3$“ → $(2,2)$: $F(2,2) = 3 = F(1,2)$, vzít dává jen $0+2=2$ → $I_2$ ne → $(1,2)$: $3 \ne F(0,2) = 0$ → $I_1$ ano → $S_1 = \{I_1\}$, cena 3, váha 2.
  • Větev „vzít $I_3$“ → $(2,1)$: $F(2,1) = 2 \ne F(1,1) = 0$ → $I_2$ ano → $(1,0)$: konec → $S_2 = \{I_2, I_3\}$, cena $2+1 = 3$, váha 2.

Řešení NENÍ unikátní: existují dvě optimální množiny $\{I_1\}$ a $\{I_2, I_3\}$, obě s cenou 3 — přesně proto, že tabulkou vedou dvě zpětné cesty (remíza v buňce $(3,2)$). Tohle je odpověď, kterou zkouška u otázky „why?“ chce slyšet: unikátnost ⟺ jediná cesta bez remíz.

← Předchozí L6.3 · AC-3 algoritmus + oditerování [FOTO]