Korektury od Martina Jiricky.

[ads2.git] / 12-apx / 12-apx.tex

diff --git a/12-apx/12-apx.tex b/12-apx/12-apx.tex
index aa6fb39d9c98aa537d9a72339e90addef9be0ab9..d2583f3aa42cab6a770deb065dd176c57d19ec98 100644 (file)
--- a/12-apx/12-apx.tex
+++ b/12-apx/12-apx.tex
@@ -71,7 +71,7 @@ c_i$.
 \>Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
 pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost
 podmno¾iny, její¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$:
-Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=\infty$ pro $c>0$. Pokud ji¾ známe
+Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=infty$ pro $c>0$. Pokud ji¾ známe
 $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
 pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili
 (a pak je $A_k(c)=A_{k-1}(c)$), nebo pou¾ili a tehdy bude $A_k(c) =
@@ -84,7 +84,7 @@ T
 v~èase $\O(nC)$ pak v¹echny $A_k(c)$.
 
 \>Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do~batohu.
-To bude nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) < \infty$. Jeho nalezení nás stojí
+To bude nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) \le H$. Jeho nalezení nás stojí
 èas $\O(C)$.
 
 \>A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus,