Dekompozice podle kapacity batohu

Nechť (Xn, Cn, m) = KNAP (V, C, M) je algoritmus řešící instanci problému batohu danou (V, C, M) a vracející vektor X, celkovou cenu Cn a celkovou váhu m. Pak můžeme KNAP napsat jako následující pseudokód, kde tečka je operátor zřetězení:

function KNAP (V, C, M)
    if isTrivial (V, C, M) return trivialKNAP (V, C, M);
    (X0, C0, m0) = KNAP (V-{vn}, C-{cn}, M);
    (X1, C1, m1) = KNAP (V-{vn}, C-{cn}, M-vn);
    if C1+cn > C0 return (X1.1,  C1+cn, m1+vn);
    return (X0.0, C0, m0);

function isTrivial (V, C, M)
    return (isEmpty (V) or M=0 or M<0);

Abychom stanovili optimální řešení pro n věcí, musíme znát
Srovnáme-li oě varianty, zjistíme, zda n-tá věc má být v optimálním řešení. Tím jsme optimální řešení instance o n prvcích převedli na optimální řešení dvou instancí o n-1 prvcích. Rekurze se zastaví u instancí, které jsou řešitelné v konstantním čase. Funkci trivialKNAP přenecháme laskavému čtenáři jako cvičení.

Až dosud uvbedený algoritmus je hledáním do šířky. Protože pokaždé voláme funkci dvakrát a hloubka rekurze je n, je složitost 2n. Nicméně, některé instance řešíme vícekrát a můžeme tedy uschovávat řešení. Protože podúlohy pracují vždy s i prvými věcmi a množiny V and C lze považovat za globální, každá podúloha je charakterizována hodnotami n a M. Proto pamět mezivýsledků můžeme uspořádat do dvourozměrného pole indexovaného hodnotami n a M. Pole má  nM prvků a taková je i složitost algoritmu. Je polynomiální ve velikosti instance, nicméně obsahuje parametr, který s velikostí instance nesouvisí. Takové algoritmy se nazývají pseudopolynomiální.

Dynamické programování mmůžebýt buď složeno z dopředné a zpětné fáze nebo může obsahovat jen zpětnou fázi. V dopředné fázi začínáme od původní úlohy v prvku (n, M) pole a rekurzivně označujeme podúlohy, které potřebujeme řešit, až narazíme na triviální podúlohy. Ve zpětné fázi vyřešíme nejprve označené triviální podúlohy (resp. všechny triviální podúlohy, nemáme-li dopřednou fázi). Pak řešíme takové označené (resp. všechny takové) úlohy, které lze řešit pomocí úloh již vyřešených a v tabulce uložených, až dospějeme k celkovému řešení.

Příklad

 Nechť n=5, V=(2,6,5,3,4), C=(5,9,20,12,18), a M = 10. Dopředná fáze začíná s prvkem (5, 10). Abychom tuto úlohu vyřešili, potřebujeme řešení (4,10), pokud pátá věc není v optimálním řešení, a (4,6) v opačném případě.Tento postup se opakuje, až dostaneme triviální podúlohy pro n=0 nebo nekladné M. Pro názornost jsou zachyceny potřebné instance se zápornými kapacitami, ačkoliv jejich řešení je konstantní a nezávislé na parametrech.

Legenda:

 
 výsledné řešení
 
 netriviální podúloha k řešení
 
 triviální podúloha k řešení
 
 triviální podúloha, jejíž řešení nepotřebujeme
 
 rekonstrukce X


10
  
  
  
  
  
  
9
  




8
  




7
  
  
  
  

6
  
  
  
  
   
5
  
  
  


4
  
  



3
  
  
  
 

2
  
  
  


1
  
  
  


0
  
  
  
  
  
  
-1
  
  
  
  
  
  
-2
  
  
  
  
  
  
-3
  
  
  
  
  
  
-4
  
  
  
  
  
  
n
 0
 1
 2
 3
 4
 5
V
2
 6
 5
 3
 4
C
5
 9
 20
 12
 18
Zpětná fáze začíná řešením triviálních podúloh a pak dalších ve směru rostoucího n. Dvojice(m, Cn) reprezentuje řešení každé podúlohy.

10
 0, 0
 2, 5
 8, 14
 7, 25
 10, 37
 9, 38
9
 0, 0




8
 0, 0




7
 0, 0
 2, 5
 6, 9
 7, 25

6
 0, 0
 2, 5
 6, 9
 5, 20
 5, 20
5
 0, 0
 2, 5
 2, 5


4
 0, 0
 2, 5



3
 0, 0
 2, 5
 2, 5
 2, 5

2
 0, 0
 2, 5
 2, 5


1
 0, 0
 0, 0
 0, 0


0
 0, 0
 0, 0
  
  
  
  
-1
 0, -inf
 0, -inf
  
  
  
  
-2
  
  
 0, -inf
  
  
  
-3
  
 0, -inf
  
  
  
  
-4
  
 0, -inf
  
  
  
  
-5
  
 0, -inf
  
  
  
  
n
 0
 1
 2
 3
 4
 5
V
2
 6
 5
 3
 4
C
5
 9
 20
 12
 18

Pokud není dopředná fáze, je třeba vyřešit podúlohy ve všech prvcích pole. Na závěr rekonstruujeme vektor X. Jestliže hodnoty v prvku (n, m) jsosu stejné jako v prvku (n-1, m), pak n-tá věc není ve výsledném řešení podúlohy charakterizované (n, m). Tento postup dá optimální řešení i v případě, že obě varianty (s n-tou věcí a bez ní) dávají týž výsledek. Přesnější postup výpočtu je na obrázku.

10
 0, 0
 2, 5
 8, 14
 7, 25
 10, 37
 9, 38
9
 0, 0
 2, 5
 8, 14
 7, 25
 8, 32
 9, 38
8
 0, 0
 2, 5
 8, 14
 7, 25
 8, 32
 8, 32
7
 0, 0
 2, 5
 6, 9
 7, 25
 7, 25
 7, 30
6
 0, 0
 2, 5
 6, 9
 5, 20
 5, 20
 6, 23
5
 0, 0
 2, 5
 2, 5
 5, 20
 5, 20
 5, 20
4
 0, 0
 2, 5
 2, 5
 2, 5
 3, 12
 4, 18
3
 0, 0
 2, 5
 2, 5
 2, 5
 3, 12
 3, 12
2
 0, 0
 2, 5
 2, 5
 2, 5
 2, 5
 2, 5
1
 0, 0
 0, 0
 0, 0
 0, 0
 0, 0
 0, 0
0
 0, 0
 0, 0
 0, 0
 0, 0
 0, 0
 0, 0
<0
 0, -inf
 0, -inf
 0, -inf
 0, -inf
 0, -inf
 0, -inf
n
 0
 1
 2
 3
 4
 5
V
2
 6
 5
 3
 4
C
5
 9
 20
 12
 18

Praktické úvahy

V tabulkách jsme pro přehlednost vynechali vektor X, který ostatně může být rekonstruovám. Podobně není nezbytné v tabulce mít sumární váhy.
Pozorný čtenář si možná všiml, že nepotřebujeme celou tabulku v paměti. Pokud do prvků zahrneme vektor X, stačí jen jeden sloupec tabulky.