Máme tedy předměty očíslované 1 až k <= 5 s cenami ci a od každého z těchto předmětů chceme nakoupit mi <= 6 kusů s využitím nabídek zlevňujících sadu tvořenou pij kusy j-tého druhu zboží na cenu wi.
Nejprve si nadefinujeme konfigurace a operace s nimi:
Naším cílem je tedy nalézt konfiguraci e, která je rozšířením zadané konfigurace m a její we je nejmenší možné. Jelikož nákup se vždy skládá ze zlevněných nabídek doplněných jednotlivými předměty, je každou konfiguraci e možno rozložit na prostou konfiguraci p a triviální konfigurace ki (vybrané z množiny všech Ti, ale některé se mohou vyskytnout vícekrát) takové, že e = p + SUMAi ki a we = wp + SUMAi wk(i). Pokud tedy dokážeme spočítat ceny wp pro všechny prosté konfigurace, máme vyhráno, protože stačí prozkoumat všechny takové a každou doplnit triviálními tak, aby obsahovala všechny požadované předměty z m a je jisté, že mezi takto získanými konfiguracemi bude i hledaná e.
Ceny prostých konfigurací spočteme indukcí podle vp. Pro prázdnou
konfiguraci (víme o ní, že vp=0) je cena nulová. Známe-li již
ceny všech prostých konfigurací qi takových,
že vq(i) < vp,
spočteme cenu prosté konfigurace p:
Jelikož optimální zaplacení každé neprázdné
prosté konfigurace zahrnuje přikoupení nějaké zlevněné nabídky k některé
menší prosté konfiguraci, stačí položit:
wp=min{ wq(i)
+ wp(j) ; qi + pj = p }
To můžeme snadno učinit,
jelikož všechna qi, která potřebujeme,
jsou v daném okamžiku již spočtena (qi < p, tudíž
také vq(i) < vp).
Zadání od nás ovšem požaduje nejen spočtení we, ale také zjištění, které nabídky jsme pro tento výpočet využili. K tomu stačí při výpočtu minima v indukčním kroku připojit informaci o tom, pro jaké i,j se minima nabývá a podle toho pak prostou konfiguraci p, jejímž rozšířením získáme optimální zaplacení e, rozložit na nabídky (odebráním poslední přidané nabídky získáme menší prostou konfiguraci, kterou rozložíme týmž způsobem).
Časová složitost: Připravná fáze (filtrování zadání) trvá O(nm), oceňování prostých konfigurací O(smk) (kde s=(1+maxi mi)k je počet všech konfigurací), ocenění zadané konfigurace O(s\cdot k) a zpětné vyhledání optimálního zaplacení O(s). Celkem tedy O((1+maxi mi)kmk + nm).
Paměťová složitost: O((1+maxi mi)k + mk + n).
Řešení pomocí frekvencí výskytů je sice rychlé, ne vždy ale najde správné řešení. Proto je poměrně vhodné spojit tuto techniku ještě s prohledáváním všech možností. Můžeme například zkusit uhádnout řešení pomocí frekvencí a pokud tímto způsobem nenajdeme správné řešení, spustíme ještě prohledávání všech možností. Případně můžeme pomocí frekvencí výskytů uhádnout délku klíče a zkoušet pak už jenom klíče této délky.
Malá písmena anglické abecedy označme čísly 0 (a)
až 25 (z). Vynechejme nyní ze zašifrovaného textu mezery
a písmena zašifrovaného textu označme po řadě
c0,c1,... ,cn-1, kde n je počet
písmen v zašifrovaném textu. Klíč budeme
označovat K = k0k1...kd-1.
Nalezení klíče se skládá ze dvou podúloh: v první fázi
musíme zjistit délku klíče d a ve druhé samotný klíč K.
Předpokládejme nyní, že známe délku klíče d. Písmena si rozdělíme do d skupin podle toho, kterým písmenem klíče byla zašifrována. První skupinu budou tedy tvořit písmena c0,cd,c2d,..., která byla zašifrována znakem klíče k0. Obecně skupinu zašifrovanou znakem klíče ki tvoří znaky ci,cd+i,c2d+i,....
Pokusíme se nyní určit písmeno ki. Pokud jím odšifrujeme jeho
skupinu písmen, měly by se jejich frekvence podobat rozdělení
frekvencí jednotlivých znaků v běžném textu. Musíme si ovšem
stanovit kritérium, které určí, nakolik se dvě rozdělení frekvencí
sobě podobají. Při statistických výpočtech se obvykle používá
následující vztah (pj je frekvence výskytu písmena j v běžném
textu, fj,ki je frekvence výskytu písmena j
v naší skupině
po odšifrování pomocí ki):
ok(i) = sqrt( (f0,k(i) - p0)2+
... + (f25,k(i) - p25)2),
přičemž frekvence se sobě podobají tím více, čím je nižší hodnota
ok(i).
Vyzkoušíme tedy, pro které ki bude tato suma
minimální (všimněme si, že platí fa,b = fa+i, b+i
pro i=0,1,...,25, + je
sčítání modulo 26; z čísel fa,b nám tedy stačí počítat jen
f0,0,f1,0,... f25,0).
Popsaným způsobem jsme schopni najít klíč pro danou délku efektivně a s velkou pravděpodobností. Popsaná metoda funguje pro dostatečně dlouhé šifrované texty, pro její spolehlivý chod stačí kolem 50 znaků šifrovaného textu na jeden znak klíče.
Zůstává problém s určením délky klíče. Nejjednodušší metodou je vyzkoušet všechny délky od 1 do určeného maxima, najít pro danou délku kandidáta na klíč, dešifrovat s ním zašifrovaný text a ověřit, zda jsme dostali text skládající se ze slov obsažených ve slovníku. Jinou možností je pokusit se určit i délku klíče statisticky - vybereme takovou délku klíče, aby statistická odchylka frekvencí výskytu písmen v textu dešifrovaném pomocí nalezeného klíče (dané délky) od hodnot pi byla minimální. Je-li řetězec K klíčem, budou klíči také KK, KKK, ... atd. Proto minimální odchylku dostaneme pro více délek, z nichž samozřejmě vybereme minimální.
Všech klíčů délky k existuje 26k, což je už pro poměrně
nízké k velmi velké číslo. Proto nemůžeme bezhlavě zkoušet
všechny možnosti. Dobré řešení dostaneme třeba takto. Náš klíč
budeme vytvářet postupně. Začneme s klíčem, v němž budou
místo písmen znaky *,
které znamenají, že dané písmeno klíče ještě není určeno (tj. může tam
být libovolné písmeno). Potom postupně po jedné budeme hvězdičky
nahrazovat písmeny, přičemž pro každou hvězdičku rekurzívně
zkoušíme všechny možnosti nahrazení ostatních hvězdiček v klíčí.
Důležité je, že vždy, když
některou hvězdičku nahradíme písmenem, zkontrolujeme konzistenci
dosud vytvořeného klíče se zašifrovaným textem (a slovníkem).
To znamená, že v každém slově zašifrovaného textu odšifrujeme
pomocí našeho klíče písmena,
která jsme již v klíči určili, a na pozice odpovídající hvězdičkám dáme
hvězdičky. Potom zjišťujeme, zda se dají hvězdičky v rozšifrovaném
slově nahradit tak, abychom dostali nějaké slovo ze slovníku
(tj. hledáme ve slovníku slovo, které se s naším nezašifrovaným
slovem shoduje na všech nehvězdičkových pozicích). Jakmile zjistíme,
že některé slovo po takovémto částečném rozšifrování nelze
doplnit na slovo ze slovníku, víme, že v našem dosud vytvořeném
klíči je některé písmeno špatně a nemá tedy smysl zkoušet v něm
nahrazovat další hvězdičky písmeny.
Zkušenosti ukazují, že pokud zkoušíme například nesprávnou délku klíče, většinou hned po dosazení prvního písmena do klíče zjistíme, že tato možnost není správná, stačí tedy vyzkoušet 26 možností. Podobně velmi rychle se tímto způsobem objeví i případ, když umístíme na některé místo chybné písmeno. Na první pohled se může zdát, že prohledávat po doplnění každého písmena do klíče každé slovo zašifrovaného textu a pro každé takové slovo ještě prohledávat velkou část slovníku se nevyplatí, ve skutečnosti nám však tímto prohledáváním ubude velmi mnoho možností.
Při tomto způsobu řešení je vhodné slovník reprezentovat tak, že slova máme rozdělena do seznamů podle délky, abychom při vyhledávání nemuseli zbytečně prohlížet i slova jiných délek. V těchto seznamech už nemusíme slova nijak speciálně uspořádávat, vyhledáváme v nich lineárně.
Popíšeme si ještě jedno možné vylepšení. Je založeno na jednoduché myšlence: slov některých délek (velmi krátkých a velmi dlouhých slov) je poměrně málo. Kdybychom text dešifrovali ručně, zkoušeli bychom na tato místa dosazovat jednotlivá slova, což by nám určilo část klíče. Takto získanou část klíče bychom se pak snažili rozšířit.
Nyní ukážeme, jak lze tuto myšlenku využít v programu. Předpokládejme například, že v zašifrovaném textu je na některém místě slovo délky 2 začínající na a a že žádné slovo délky 2 obsažené ve slovníku nezačíná písmenem z. Z toho vyplývá, že v klíči na pozici, která se při šifrování umístí pod dané místo textu, určitě nebylo písmeno b, neboť pomocí písmena b jsme písmeno a mohli dostat jedině z písmena z (a písmeno z na dané pozici být nemůže).
Podobných omezení můžeme na základě slovníku najít více a pro každou pozici klíče vytvoříme seznam hodnot, které se na tomto místě v klíči mohou vyskytnout. V příznivém případě se stane, že na některé pozici nám nezůstane žádná možnost - znamená to, že jsme zvolili nesprávnou délku klíče a je třeba zkoušet jinou.
Jestliže však máme pro každou pozici klíče aspoň jednu možnost, můžeme použít získané informace při prohledávání. Prohledáváme v podstatě stejně jako předtím - vždy dosadíme jedno písmeno do klíče a ověříme správnost klíče. Zkoušíme však už jen ty možnosti, které jsme dosud nevyloučili. Navíc je výhodné začít těmi pozicemi klíče, které mají nejméně možností.
Pro přirozené texty se při tomto způsobu řešení často stává, že pro nesprávnou délku klíče získáme pro některou pozici nula možností, takže k samotnému prohledávání ani nedojde. Naopak, když zkoušíme správnou délku klíče, pro mnohé (někdy dokonce pro všechny) pozice zůstane jen jedna možnost, kterou můžeme přímo do klíče dosadit.