L7.2 Kapitola K7 — Knapsack (doplňková) · [NICE]

Knapsack DP indexovaný cenou (cost-indexed)

Jedna nová věc DP tabulka indexovaná cenou: buňka $x_k^j$ = minimální váha, kterou lze dosáhnout ceny přesně $k$ výběrem z položek $1..j$ — duál ke kapacitní tabulce z [L7.1], složitost $O(nC)$, optimum se čte jako nejpravější dosažitelná cena posledního řádku.

V [L7.1] Knapsack DP (tabulka + backtracking) jsi vyplňoval tabulku položky × kapacita a v každé buňce maximalizoval cenu. Přednáška (slidy 8–9) ale předvádí DP pro batoh primárně v opačné orientaci — a právě tahle orientace je základem aproximačního schématu (FPTAS), které samo navazuje na 2-aproximaci z [L3.11]. Nejdřív ale proč vůbec tabulku otáčet:

Otočení tabulky: co když váhy nejsou hezká celá čísla?

Zkus sám: kapacitní tabulka z [L7.1] má sloupce $W' = 0, 1, \ldots, W$ — to vyžaduje celočíselné váhy. Co uděláš, když váhy jsou reálné (třeba $w = (2{,}7;\ 3{,}14;\ \ldots)$), ale ceny jsou malá celá čísla?

Prohodíš role: sloupce nebudou kapacity, ale ceny $k = 0, 1, \ldots, C$ (kde $C$ je nějaká horní mez optima, třeba $\sum_j c_j$). A protože cena je teď „adresa sloupce“, nemůže být zároveň hodnotou buňky — do buňky se ukládá to druhé, co o výběru potřebuješ vědět: váha. Tabulka diskretizuje tu veličinu, která je celočíselná; druhá smí být libovolná reálná. Přesně proto slide 9 deklaruje vstup jako $c_1, \ldots, c_n \in \mathbb{Z}_0^+$, ale $w_1, \ldots, w_n, W \in \mathbb{R}_0^+$.

Zkus sám: ve sloupci ceny $k$ se může „srazit“ víc výběrů se stejnou cenou. Kterého zástupce si buňka má pamatovat — a proč právě toho?

Nejlehčího. Všechny výběry s cenou $k$ jsou v cílové funkci k nerozeznání; liší se jen tím, kolik kapacity spotřebují — a méně je vždy bezpečnější (lehčí výběr projde kapacitním testem $\le W$ kdykoli projde těžší a nechává víc místa zbytku položek). Buňka tedy minimalizuje váhu, zatímco v kapacitní tabulce maximalizovala cenu: směr optimalizace v buňce se otočil spolu s tabulkou. To je zase „diamond“ ze slidu 10: dvě cesty stavovým prostorem do téhož stavu, necháváme si lepší.

Definice ze slidu 8 (EN 1:1): “Variable $x_k^j$ represents the minimum weight with cost $k$ which can be achieved as a selection of items from set $\{1, \ldots, j\}$.” Ceny, kterých z položek $1..j$ dosáhnout nejde, mají $x_k^j = \infty$.

Rekurence, kapacitní filtr a bit $s_k^j$

Rozhodnutí o položce $j$ je stejné „vzít / nevzít“ jako v [L7.1] — jen se obě větve čtou v řeči vah (slide 8, EN 1:1):

$$x_k^j = \begin{cases} x_{k - c_j}^{j-1} + w_j & \text{if item } j \text{ was added;} \\ x_k^{j-1} & \text{if item } j \text{ wasn't added.} \end{cases}$$

Kdy se položka přidá, říká podmínka (*) ze slidu 8 (EN 1:1): “Item $j$ is added to the selection of items from $1, \ldots, j$ if for the given price $k$ this set reaches the lower or equal weight as set $1, \ldots, j-1$.” V pseudokódu je to test $x_{k-c_j}^{j-1} + w_j \le \min\{W,\ x_k^{j-1}\}$ — a do bitu $s_k^j$ se zapamatuje, která větev vyhrála (slide 8: “In variable $s_k^j$ we memorize which of the two possible cases has happened. It is later used to reconstruct the selection.”).

Zkus sám: proč je v testu $\min\{W,\ x_k^{j-1}\}$, a ne jen $x_k^{j-1}$? Co by se rozbilo bez té $W$?

Je to kapacitní filtr: výběr s váhou $> W$ se do batohu nikdy nevejde, takže nemá smysl ho ukládat — buňka by lhala, že cena $k$ je dosažitelná. Díky filtru platí invariant každá konečná hodnota v tabulce je $\le W$, a proto se na konci optimum smí číst prostě jako největší $k$ s $x_k^n < \infty$ — bez dodatečné kontroly přípustnosti. (V kapacitní tabulce [L7.1] filtr nebyl potřeba: tam přípustnost hlídaly samy sloupce $W' \le W$.) A proč $x_{k-c_j}^{j-1}$ čte řádek $j-1$, ne $j$? Stejný důvod jako v [L7.1]: 0/1 batoh — čtení vlastního řádku by položku $j$ přidávalo opakovaně (unbounded).

Celý algoritmus ze slidu 9 (EN 1:1, vstup/výstup i pseudokód):

Dynamic Programming (Integer Costs) for Knapsack — slide 9, EN 1:1

Input: Costs $c_1, \ldots, c_n \in \mathbb{Z}_0^+$, weights $w_1, \ldots, w_n, W \in \mathbb{R}_0^+$.
Output: $S \subseteq \{1, \ldots, n\}$; $\sum_{j \in S} w_j \le W$ and $\sum_{j \in S} c_j$ is maximum.

Let C be the arbitrary upper bound of the solution, e.g. C = sum_{j=1}^{n} c_j;
x_0^0 := 0; x_k^0 := infinity for k = 1, ..., C;
for j := 1 to n do
    for k := 0 to C do  x_k^j := x_k^{j-1}; s_k^j := 0 ;
    for k := c_j to C do
        if x_{k-c_j}^{j-1} + w_j <= min{W, x_k^{j-1}} then
            x_k^j := x_{k-c_j}^{j-1} + w_j; s_k^j := 1;
        end
    end
end
i := max{k in {0, ..., C} : x_k^n < infinity}; S := empty;
for j := n downto 1 do
    if s_i^j = 1 then S := S union {j}; i := i - c_j;
end

Kde je optimum? (Tentokrát NE v rohu)

Zkus sám: v kapacitní tabulce bylo optimum vždy v pravém dolním rohu $(n, W)$. Kde se čte z tabulky indexované cenou — a proč roh nefunguje?

Sloupce jsou teď ceny a cena je cílová funkce: chceš nejpravější sloupec posledního řádku, který je vůbec dosažitelný — $i := \max\{k : x_k^n < \infty\}$ (díky kapacitnímu filtru je každá konečná buňka automaticky $\le W$). Pravý dolní roh je sloupec $k = C$, a $C$ je jen horní mez (např. $\sum_j c_j$ = „vezmu úplně všechno“) — té většinou žádný přípustný výběr nedosáhne, takže v rohu typicky sedí $\infty$. Přesně na tohle mířila červená poznámka studenta u zkouškové úlohy (citovaná v řešení T01 lekce [L7.1]): „opt. řešení nemusí být v pravém dolním rohu.“

Krok za krokem: blackboard example ze slidu 8

Slide 8 dává k tabuli instanci (integer costs): $n = 4$, $w = (21, 35, 52, 17)$, $c = (10, 20, 30, 10)$, $W = 100$ — instance je ze slidu, vyplnění a krokování níže je naše (přiznáno). Mez $C = \sum c_j = 70$. Všechny ceny jsou násobky 10, takže dosažitelné jsou jen sloupce $k \in \{0, 10, \ldots, 70\}$ — kreslíme jen ty (formálně je to substituce $c'_j = c_j / 10$, tedy zaokrouhlovací trik ze slidu 11 s $t = 10$, zde beze ztráty, protože 10 dělí všechny ceny — k tomu se vrátíme dole).

Unikátnost: tahle tabulka umí mlčet

Zkus sám: poslední krok stepperu ukázal druhé optimum $\{I_1, I_3, I_4\}$ (cena 50, váha $90 \le 100$), které v tabulce není vidět — žádná remíza. Proč pravidlo z [L7.1] „unikátní ⟺ žádná remíza na zpětné cestě“ tady selhává? A kdy přesto platí?

Buňka si pamatuje jen nejlehčího zástupce dané ceny. Výběr se stejnou cenou a vyšší váhou prohraje souboj o buňku a zmizí — ale pokud jeho váha pořád je $\le W$, je to plnohodnotné optimum (cílová funkce váhu nehodnotí!). U nás: na $(I_4, k{=}50)$ kandidát „vzít“ s váhou $x_{40}^3 + 17 = 73 + 17 = 90$ prohrál s 87, žádná remíza nevznikla, a přitom $90 \le 100$ — druhé optimum spolklo. Remíza (rovnost vah) tedy pořád zaručuje více optim, ale její absence unikátnost nezaručuje. Kdy absence remíz stačí? Třeba když $x_i^n = W$ přesně: pak každé optimum musí vážit právě $W$ (mezi minimem a $W$ není místo), dvě různá optima by se v buňce posledního rozdílu potkala se stejnou vahou — a to už remíza je. Jinak je potřeba prohrávající větve na zpětné cestě zkontrolovat ručně (vejde se i s dokončením pod $W$?), nebo argumentovat kombinatoricky výčtem (T02).

Pozor: čím se cost-indexed tabulka liší (a kde se ztrácí body)

Složitost $O(nC)$ — a kterou tabulku kdy vytáhnout

Zkus sám: kolik buněk má cost-indexed tabulka a co to znamená pro složitost? A rozhodni: instance se sliby (a) „celé váhy, $W \le 10n$“, (b) „celé ceny, $c_j \le 5$“ — kterou tabulkou na kterou?

$(n+1)(C+1)$ buněk, konstantní práce na buňku → $\mathcal{O}(nC)$ (slide 8); rekonstrukce $O(n)$. Stejný příběh jako u $O(nW)$ v [L7.1]: $C$ je číslo zapsané v $O(\log C)$ bitech, takže algoritmus je pseudopolynomiální [L3.5] — tentokrát v cenách, ne ve vahách. (a) $W \le 10n$ zkrotí kapacitní tabulku: $O(nW) = O(n^2)$ — sliby o $W$ cost-indexed tabulce nepomáhají, její velikost řídí $C$. (b) $c_j \le 5$ dává $C = \sum c_j \le 5n$, tedy $O(nC) = O(n^2)$ pro cost-indexed — a kapacitní tabulka může být obrovská, je-li $W$ veliké. Pravidlo: tabulku indexuj tou veličinou, která je celočíselná a malá; každý slib v zadání ($W \le 10n$, malé ceny, …) je nápověda, kterou orientací počítat. U našeho příkladu: kapacitní tabulka $5 \times 101 = 505$ buněk, cost-indexed po vydělení deseti $5 \times 8 = 40$.

Výhled: proč je tahle varianta základ FPTAS

Složitost $O(nC)$ visí na velikosti cen — a ceny jdou zmenšit zaokrouhlením. Slide 11 (EN 1:1): “Divide all costs $c_1, \ldots, c_n$ by 2 and round them down. The algorithm becomes faster, but we can obtain a suboptimal solution.” Obecně $\bar{c}_j := \lfloor c_j / t \rfloor$ zrychlí DP $t$-krát za cenu ztráty přesnosti — tím vzniká volitelný kompromis rychlost × kvalita. Aproximační schéma ze slidu 12 pak: ① spustí 2-aproximaci [L3.11] a jejím výsledkem $c(S_1)$ zkalibruje $t := \max\{1, \frac{\epsilon\, c(S_1)}{n}\}$ a mez $C := \frac{2c(S_1)}{t}$, ② pustí toto DP na zaokrouhlených cenách, ③ vrátí lepší z obou řešení — výsledkem je $(1+\epsilon)$-aproximace v $O(n^2 \cdot \frac{1}{\epsilon})$ (slide 13). Klíčové pro dnešek: zaokrouhlují se ceny, proto schéma potřebuje DP indexované cenou — kapacitní tabulce by zaokrouhlení cen velikost nezmenšilo. Víc do hloubky FPTAS nejdeme (pro 15. 6. stačí vědět, že existuje a jak do sebe kroky zapadají).

Key takeaways — L7.2
T01 Formulace DP s celočíselnými cenami zdroj: task bank #28 (study task ze slidů 8–9), zadání EN 1:1
Assignment (original, EN)

“Given costs $c_1, \ldots, c_n \in \mathbb{Z}_0^+$, weights $w_1, \ldots, w_n$, and capacity $W$, formulate the dynamic-programming algorithm based on integer costs. Let $C$ be an upper bound on the solution value, for example

$$C = \sum_{j=1}^{n} c_j.$$

Define the DP state $x_k^j$, give the recurrence and initialization, explain how the selected set is reconstructed from $s_k^j$, and state the time complexity.”

a) Co je v zadání?

Teoretická (ústní) otázka: zformulovat cost-indexed DP pro 0/1 batoh — definice stavu, rekurence s inicializací, rekonstrukce výběru z bitů $s_k^j$ a složitost. Žádná čísla, čistě formulace.

b) Co k tomu budeme potřebovat?

  • Tato lekce — definice $x_k^j$, podmínka (*), pseudokód, čtení optima, $O(nC)$.
  • [L3.5] Silná NP-těžkost — zařazení „pseudopolynomiální“.

c) Jak nad úlohou uvažovat?

Odpověz strukturou ze zadání: ① stav, ② rekurence + inicializace (nezapomeň kapacitní filtr $\min\{W, \cdot\}$ — bez něj je formulace špatně), ③ kde se čte optimum (ne roh!), ④ rekonstrukce, ⑤ složitost a proč pseudopolynomiální. Zkus si to říct nahlas bez koukání, pak porovnej.

d) Úplné řešení

① Stav. $x_k^j$ = minimální váha, které lze dosáhnout výběrem z položek $\{1, \ldots, j\}$ s celkovou cenou přesně $k$, pro $j = 0..n$, $k = 0..C$ (slide 8: “minimum weight with cost $k$ which can be achieved as a selection of items from set $\{1,\ldots,j\}$”); nedosažitelné ceny mají $\infty$.

② Inicializace a rekurence. $x_0^0 := 0$, $x_k^0 := \infty$ pro $k = 1..C$. Pro $j = 1..n$ nejdřív celý řádek opiš ($x_k^j := x_k^{j-1}$, $s_k^j := 0$) a pak pro $k = c_j..C$:

$$\text{if } x_{k-c_j}^{j-1} + w_j \le \min\{W,\ x_k^{j-1}\} \text{ then } x_k^j := x_{k-c_j}^{j-1} + w_j;\ s_k^j := 1.$$

Tedy položka $j$ se přidá, pokud pro danou cenu $k$ dosáhne nižší nebo stejné váhy (podmínka (*)) — a $\min\{W, \cdot\}$ zároveň filtruje výběry, které se do batohu nevejdou: každá konečná hodnota tabulky je $\le W$.

③ Optimum. $i := \max\{k \in \{0,\ldots,C\} : x_k^n < \infty\}$ — nejvyšší dosažitelná (a díky filtru automaticky přípustná) cena. Pozor, není to pravý roh tabulky: sloupce $k$ blízko $C$ bývají $\infty$.

④ Rekonstrukce z $s_k^j$. Začni $i$ v posledním řádku, $S := \emptyset$; pro $j = n$ dolů k $1$: je-li $s_i^j = 1$, byla položka $j$ při ceně $i$ vzata → $S := S \cup \{j\}$ a $i := i - c_j$ (přesun do sloupce, ze kterého rekurence četla); jinak jen o řádek výš. Po $j = 1$ je $S$ hledaný výběr.

⑤ Složitost. $(n+1)(C+1)$ buněk, $O(1)$ na buňku → $\mathcal{O}(nC)$, rekonstrukce $O(n)$. Protože $C$ je hodnota zapsaná na $O(\log C)$ bitech, je algoritmus pseudopolynomiální [L3.5]. Mez $C$ smí být libovolná horní mez optima — default $\sum_j c_j$; těsnější mez (např. $2\,c(S_1)$ z 2-aproximace [L3.11], jak to dělá aproximační schéma slidu 12) tabulku zmenší.

T02 Zkoušková instance podruhé — cost-indexed tabulkou zdroj: zkouška 2023 (str. 4, úloha 6b), zadání EN 1:1 — táž instance jako T01 v [L7.1], zde řešená druhou orientací tabulky (volba orientace naše, přiznáno; zadání konkrétní tabulku nepředepisuje)
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í?

Stejná zkoušková instance jako v [L7.1] T01 — tam vyřešená kapacitní tabulkou (optimum 8, $\{I_1, I_2, I_5\}$, unikátní). Tady ji projdeš cost-indexed tabulkou: jednak jako drill dnešní lekce, jednak abys viděl, že obě orientace dají totéž — a že otázka b) je vlastně test, kterou orientaci sliby zadání zvýhodňují.

b) Co k tomu budeme potřebovat?

  • Tato lekce — rekurence, kapacitní filtr, čtení optima, rekonstrukce, unikátnost.
  • [L7.1] — výsledek ke kontrole + odpověď b) pro kapacitní tabulku.

c) Jak nad úlohou uvažovat?

Mez $C = \sum c_j = 16$ → tabulka $8$ řádků ($j = 0..7$) × $17$ sloupců ($k = 0..16$). Vyplňuj po řádcích; u každého $k \ge c_j$ proveď test s $\min\{W{=}5, \cdot\}$ — hlídej remízy (rovnost vah) kvůli unikátnosti. Pak najdi nejpravější konečnou buňku posledního řádku a rekonstruuj podle bitů $s$. Pro b) si rozmysli, které tabulce slib $W \le 10n$ vůbec pomáhá. Nejdřív na papír, pak krokuj.

d) Úplné řešení

a) Všechny iterace (kroky 1–8 vyplnění řádků, 9–14 rekonstrukce):

Čtení optima: $i = \max\{k : x_k^7 < \infty\} = \mathbf{8}$ (sloupce $9..16$ jsou $\infty$), $x_8^7 = 5 \le W$. Rekonstrukce: $s_8^7 = 0$, $s_8^6 = 0$, $s_8^5 = 1$ → $I_5$, $i = 4$; $s_4^4 = 0$, $s_4^3 = 0$, $s_4^2 = 1$ → $I_2$, $i = 2$; $s_2^1 = 1$ → $I_1$, $i = 0$. Tedy

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

— přesně výsledek kapacitní tabulky z [L7.1] T01 (i ruční zkouškové tabulky a banky #27).

Unikátnost: ANO. Tady je potřeba dnešní opatrnost: remízy vah v tabulce jsou — $(I_2, k{=}2)$: $\{I_1\}$ vs. $\{I_2\}$, váha 1; $(I_4, k{=}6)$ a $(I_5, k{=}6)$: váha 4 — ale žádná neleží na zpětné cestě (cesta jde sloupci $8 \to 8 \to 8 \to 4 \to 4 \to 4 \to 2 \to 0$ a v každé buňce je rozhodnutí jednoznačné: vzít je buď vynucené, $x_k^{j-1} = \infty$, nebo prohrává ostře). A protože $x_8^7 = 5 = W$ přesně, skryté těžší dvojče tu nehrozí: každé optimum musí vážit právě 5 (mezi minimální vahou 5 a $W = 5$ není místo), takže druhé optimum by na cestě vyrobilo remízu — a ta tam není. Kombinatorická kontrola jako v [L7.1]: cenu 8 složíš jen jako $2{+}2{+}4$ (váha 5 ✓), $2{+}2{+}2{+}2$ (váha 6 ✗) nebo $4{+}3{+}1$ (váha 8 ✗).

b) Slib $W \le 10n$ mluví o vahách, takže pomáhá kapacitní tabulce: $O(nW) \le O(n \cdot 10n) = O(n^2)$ — polynomiální na této třídě instancí (odpověď zkoušky, viz [L7.1] T01). Dnešní cost-indexed algoritmus běží v $O(nC)$ a $W \le 10n$ jeho velikost nijak neomezuje ($C = \sum c_j$ může růst dál) — správná strategie u zkoušky je tedy na b) odpovídat kapacitní tabulkou. Mimochodem zde: kapacitní tabulka $8 \times 6 = 48$ buněk vs. cost-indexed $8 \times 17 = 136$ — i pro ruční počítání tu vyhrává [L7.1].

← Předchozí L7.1 · Knapsack DP (tabulka + backtracking)