Cím:	Mit rakjunk a hátizsákba, hogyan váltsunk fel pénzt ? II.rész
Szerző(k):	Vízvári Béla
Füzet:	1996/november, 452 - 457. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.     5. Merre menjünk?     ${}^{*}$A cikk első része októberi számunkban (386‐391. o.) olvasható. El akarunk menni Gyuláról Sopronba a lehető legrövidebb úton. Ebbe a legrövidebb útba esik Kecskemét, majd Győr. Ekkor biztos, hogy az útnak ezen két utóbbi város közé eső szakasza egyben a legrövidebb út Kecskemét és Győr között. Ha ugyanis lenne a két város között egy még rövidebb út, akkor erre kicserélve a Gyula-Sopron út Kecskemét-Győr szakaszát, Gyula és Sopron között egy még rövidebb utat kapnánk. Ha ki akarunk fizetni 190 Ft-ot a lehető legkevesebb számú pénzdarabbal, és már eldöntöttük, hogy adunk 1 db 100 forintost és 1 db 50 forintost, akkor a maradék 40 Ft-ot a lehető legkevesebb darab pénzzel kell kifizetni, ahogy 40 Ft-ot egyáltalán ki lehet fizetni, különben a megoldásunknál még jobb megoldás létezik, vagyis a mienk nem optimális. Hasonló a helyzet a hátizsákkal is. Ha bizonyos tárgyakról már eldöntöttük, hogy berakjuk-e azokat, akkor a maradék tárgyakkal a lehető legjobban kell kitölteni a maradék súlykorlátot ahhoz, hogy optimális megoldást kapjunk. Mindhárom esetben az optimális megoldást döntések sorozatán keresztül tudjuk megtalálni. Például Gyulán úgy döntünk, hogy először Kecskemétre megyünk, majd ott Győr felé vesszük az utunkat, s onnan Sopronba. Tehát az útirány felől döntünk Gyulán, Kecskeméten és Győrben, az út teljes hossza pedig ezen döntések nyomán kialakuló három útszakasz hosszának összege lesz. A 190 Ft kifizetésénél, ha használunk egy 100 és egy 50 forintost, akkor a maradék 40 Ft-ot illetően már szabad kezünk van, és az összesen felhasznált pénzdarab száma a 150 Ft-hoz és a 40 Ft-hoz használt pénzdarabok számának összege lesz. Ha az elvihető tárgyakat két részhalmazra bontjuk fel, és először az egyik részhalmaz felől döntünk, majd csak azután a másikról, akkor az elvitt tárgyak összértéke a két részhalmazból kapott értékek összege lesz. Mindhárom példa azzal a fontos közös tulajdonsággal rendelkezik, hogy az egymást követő döntések eredményei összegződnek. Az a megfigyelés, hogy a Gyula és Sopron közötti legrövidebb út Kecskemét és Győr közötti szakasza egyben a Kecskemét és Győr közötti legrövidebb út is, és ha 190 Ft kifizetésekor csak 40 Ft maradt, akkor ezt az összeget a lehető legkevesebb pénzdarabbal kell kifizetni, és hogy a második részhalmazzal a lehető legjobban kell kitölteni a hátizsák megmaradt kapacitását, speciális esete egy döntési sorozatokra vonatkozó általános optimalitási feltételnek, amelyet felfedezője után Bellman-elvnek neveznek. A Bellman-elv azt mondja ki, hogy egy optimális döntési sorozat bármely összefüggő részsorozata is optimális a részsorozatot megelőző döntések által kialakított helyzetben. (Az a kifejezés, hogy a ,,részsorozatot megelőző döntések által kialakított helyzetben'' azt jelenti például, hogy a Kecskemét-Győr szakasz optimalitásáról csak akkor beszélhetünk, ha a korábbi döntések hatására Gyuláról eljutunk Kecskemétre.) Ezen elv segítségével először a (7) feladatot oldjuk meg.${}^{*}$ld. 1996/7. sz. 391. o. Legyen $y$ egy $0$ és $b$ közé eső egész. Tekintsük azt a feladatot, amely csak abban tér el (7)-től, hogy az egyenlőség jobb oldalán $b$ helyett $y$ áll: $\begin{array}{c}{\displaystyle \begin{array}{cccccccc}\hfill \underset{}{\overset{}{\text{min}}}\hfill & \hfill (c_1{x}_1\hfill & \hfill +\hfill & \hfill c_2{x}_2\hfill & \hfill +\hfill & \hfill \text{...}\hfill & \hfill +\hfill & \hfill c_n{x}_n)\hfill \\ \hfill \hfill & \hfill a_1{x}_1\hfill & \hfill +\hfill & \hfill a_2{x}_2\hfill & \hfill +\hfill & \hfill \text{...}\hfill & \hfill +\hfill & \hfill a_n{x}_n\hfill & \hfill =\hfill & \hfill y\hfill \\ \multicolumn{9}{c}{\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow></math>}\mathrm{,}\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow></math>}\mathrm{,}\text{...}\mathrm{,}\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></math><math xmlns="http://www.w3.org/1998/Math/MathML"><mo>≥</mo></math>0}}\\ \multicolumn{9}{c}{\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow></math>}\mathrm{,}\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow></math>}\mathrm{,}\text{...}\mathrm{,}\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>n</mi></mrow></msub></mrow></math>}egész\mathrm{.}}\end{array}}\end{array}$ (8) A Bellman-elv szerint, ha valamely nemnegatív egész $w_1\mathrm{,}\text{...}\mathrm{,}{w}_n$ számokhoz a (7) feladatnak van olyan olyan $x_1^{*}\mathrm{,}\text{...}\mathrm{,}{x}_n^{*}$ optimális megoldása, amelyekre teljesül hogy $\begin{array}{c}{\displaystyle w_1\le x_1^{*}\mathrm{,}\text{...}\mathrm{,}{w}_n\le x_n^{*}\mathrm{,}\text{ és }{a}_1{w}_1+a_2{w}_2+\text{...}+a_n{w}_n=y\mathrm{,}}\end{array}$ akkor a $w_1$, $\text{...}$, $w_n$ számok a (8) feladat optimális megoldását adják, továbbá az $x_1^{*}-w_1$, $\text{...}$, $x_n^{*}-w_n$ számok pedig annak a (8) alakú feladat megoldását, amelyben az egyenletben a jobb oldal értéke $b-y$. Jelölje $f\left(y\right)$ a célfüggvénynek az optimális megoldáshoz tartozó értékét. Az $f\left(y\right)$ függvény értékét fogjuk kiszámolni minden $0$ és $b$ közé eső $y$ egész mellett. Ez első látásra elég nagy pazarlásnak tűnik, hiszen nekünk valójában az $f$ függvény egyetlen értékére van szükségünk, arra nevezetesen, amikor $y=b$. Látni fogjuk azonban, hogy furcsa módon egyszerűbb valamennyi értéket kiszámolni, mint csak egyetlen egyet. Ha $y=0$, akkor nyilvánvalóan az egyetlen megoldás, ami az összes feltételt kielégíti az $x_1^{*}=\mathrm{0,}\text{...}\mathrm{,}{x}_n^{*}=0$. Tehát ez egyben optimális is. Legyen $\widehat{y}$ egy 1 és $b$ közé eső egész. Tegyük fel, hogy ismerjük a (8) feladat megoldását az $y=\mathrm{0,1,}\text{...}\mathrm{,}\widehat{y}-1$ esetekben. Ekkor az $y=\widehat{y}$ jobb oldalhoz tartozó $x_1^{*}\mathrm{,}\text{...}\mathrm{,}{x}_n^{*}$ optimális megoldás minden eleme nem lehet 0, azaz legalább 1 pozitív eleme van. Tegyük fel, hogy ez $x_j^{*}$, tehát a Bellman-elv szerint az $x_1^{*}\mathrm{,}\text{...}\mathrm{,}{x}_{j-1}^{*}\mathrm{,}{x}_j^{*}-\mathrm{1,}{x}_{j+1}^{*}\mathrm{,}\text{...}\mathrm{,}{x}_n^{*}$ értékek a $\widehat{y}-a_j$ jobb oldalhoz tartozó optimális megoldást adják. Innen az $\widehat{y}$ jobb oldalhoz tartozó optimális érték, azaz $f\left(\widehat{y}\right)$ kiszámítására a következő szabályt nyerjük: Meg kell nézni, hogy mekkora az $\widehat{y}-a_1$, $\text{...}$, $\widehat{y}-a_j$, $\text{...}$, $\widehat{y}-a_n$ jobb oldalakhoz tartozó optimális érték, feltéve, hogy a jobb oldal egyáltalán szóba jöhet, azaz a $j$ index mellett $\widehat{y}-a_j\ge 0$ teljesül, ezen értékekhez kell rendre hozzáadni a $c_1$, $\text{...}$, $c_j$, $\text{...}$, $c_n$ számokat, és az így keletkező mennyiségek közül kell kiválasztani a legkisebbet. Okfejtésünk eredményét az alábbi képletekben fogalmazhatjuk meg: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{ccc}\hfill {\displaystyle f\left(0\right)}& {\displaystyle =0}\hfill & \hfill {\displaystyle \left(9\right)}\\ \hfill {\displaystyle f\left(\widehat{y}\right)}& {\displaystyle =\underset{}{\overset{}{\text{min}}}\left\{f\left(\widehat{y}-a_j\right)+c_j\mid \widehat{y}-a_j\ge \mathrm{0,}1\le j\le n\right\}\widehat{y}=\mathrm{1,2,}\text{...}\mathrm{,}b\mathrm{.}}\hfill & \hfill {\displaystyle \left(10\right)}\end{array}}}\end{array}$ A (9) képletből kiindulva a (10) azonnal számítható minden $\widehat{y}=\mathrm{1,}\text{...}\mathrm{,}b$ esetén, ebben a sorrendben. Érdekes megvizsgálni, hogy így hány művelet elvégzésére van szükség ahhoz, hogy az $f\left(b\right)$ értéket meg tudjuk határozni. A $b=0$ jobb oldalhoz tartozó $f\left(0\right)$ érték adott, tehát a (10) képletet pontosan $b$ számú jobb oldal esetén kell kiszámítani. Mindegyikhez legfeljebb $n$ összeadást és az ezek minimumának kiválasztásához $n-1$ összehasonlítást kell elvégezni. Legfeljebb $n$ összehasonlítás kell annak eldöntésére is, hogy az $\widehat{y}-a_j$ értékek nemnegatívak-e. (Számítógéppel történő számolás esetén ezt valamilyen formában meg kell csinálni.) Tehát a szükséges műveletek mennyiségét $nb$ összeadással és $\left(2n-1\right)b$ összehasonlítással becsülhetjük felülről. (Azért szokás a különböző műveleteket külön-külön kezelni, mert számítógépen különböző az elvégzésükhöz elhasznált idő.) A hátizsák feladat korábban említett nehéz volta itt úgy jelenik meg, hogy az elvégzendő műveletek száma arányos a feladat egyik adatával, az egyenlet jobb oldalával. Ha tehát ez nagyon nagy, akkor sok műveletet kell elvégezni. A gyakorlatban az eljárás bizonyos határokon belül gyorsan számol. Arról azonban nincs ismeretünk, hogy ez volna a hátizsák feladat megoldásának leghatékonyabb módszere. Eddig csak a célfüggvény optimális értékét határoztuk meg, de nem magát az optimális megoldást. Pedig az eljárás melléktermékeként ez is könnyen megkapható. Szükségünk lesz az optimalizálási feladatok kapcsán bevezetett következő jelölésre: Legyen $S$ egy tetszőleges halmaz, $g$ pedig egy ezen a halmazon értelmezett valós függvény, amelyhez létezik olyan $u$ és $v$ eleme az $S$ halmaznak, hogy a halmaz bármely $x$ eleme esetén $g\left(u\right)\le g\left(x\right)$, illetve $g\left(v\right)\ge g\left(x\right)$, azaz $u$, illetve $v$ optimális megoldása a $\begin{array}{c}{\displaystyle \underset{}{\overset{}{\text{min}}}\left\{g\left(x\right)\mid x\in S\right\}\mathrm{,}\text{illetve}\underset{}{\overset{}{\text{max}}}\left\{g\left(x\right)\mid x\in S\right\}}\end{array}$ feladatnak. Jelölje $\text{argmin}\left\{g\left(x\right)\mid x\in S\right\}$, illetve $\text{argmax}\left\{g\left(x\right)\mid x\in S\right\}$ ezen feladatok egy optimális megoldását. A (10) képletet úgy foghatjuk fel, hogy a $g$ függvény értéke a $f\left(\widehat{y}-a_j\right)+c_j$ érték, és a függvényt az indexek $S=\left\{\mathrm{1,2,}\text{...}\mathrm{,}n\right\}$ halmazán értelmezzük. Ezért, ha az eljárást kiegészítjük a $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle h\left(\widehat{y}\right)=\text{argmin}\left\{f\left(\widehat{y}-a_j\right)+c_j\mid \widehat{y}-a_j\ge \mathrm{0,}1\le j\le n\right\}}\\ \hfill {\displaystyle \widehat{y}=\mathrm{1,}\mathrm{2,}\text{...}\mathrm{,}b}\end{array}}}\end{array}$ utasítással, akkor azon változók indexeit őrizzük meg, amelyeket 1-gyel megnövelve kapjuk az új jobb oldal optimális megoldását. Ezért a keresett optimális megoldást úgy állíthatjuk elő, hogy $b$-ből visszafelé haladva megszámláljuk, hogy melyik változót hányszor kellett növelni. Innen az alábbi algoritmust kapjuk: begin for $j:=1$ to $n$ do $x_j=0$; $y:=b$; while $y>0$ do begin $x_{h\left(y\right)}:=x_{h\left(y\right)}+1$; $y:=y-a_{h\left(y\right)};$ $\text{end}$ end A módszer tárgyalásakor kihasználtuk, hogy a legkisebb együttható, azaz $a_1$, éppen 1. Ezért bizonyos, hogy bármely $b$ jobb oldal mellett vannak olyan $x_1$, $\text{...}$, $x_n$ nemnegatív egészek, amelyek kielégítik az egyenletet. A módszer kis módosítással akkor is alkalmazható, ha ez a feltétel nem teljesül. Legyen $M$ egy nagyon nagy szám, amely biztosan nagyobb, mint bármely optimális megoldás értéke. Ekkor az induló értéket megadó (9) képletet így kell módosítani: $\begin{array}{c}{\displaystyle f\left(0\right)=\mathrm{0,}f\left(y\right)=M\mathrm{,}y=\mathrm{1,}\text{...}\mathrm{,}b}\end{array}$ (11) Ha az algoritmus végén valamely $y$ esetén $f\left(y\right)$ még mindig $M$, akkor az egyenlet ezen jobb oldal mellett nemnegatív egészekkel nem elégíthető ki. Befejezésül a Bellman-elvet a hátizsák feladat megoldására használjuk fel. A feladat adatairól feltesszük, hogy pozitívak. Most óvatosabban kell eljárnunk, mint előzőleg. Egy bizonyos tárgy elvitelére vonatkozó döntés meghozatalakor ugyanis nem elég csak azt figyelembe venni, hogy a hátizsák kapacitásának egy meghatározott $y$ részét hogyan lehet a legjobban kitölteni, hanem biztosítani kell, hogy ebben a legjobb kitöltésben a vizsgált tárgy ne legyen benne. Ezért két részre osztjuk a tárgyakat. Az egyik részről éppen most döntünk, ezek lesznek az $\mathrm{1,}\text{...}\mathrm{,}k\mathrm{,}k+1$ indexűek, és a másik részről azt gondoljuk, hogy már döntöttünk. Az utóbbiak a $k+\mathrm{2,}\text{...}\mathrm{,}n$ indexűek. Ennek megfelelően legyen $k$ egy $1$ és $n$ közé eső, $y$ pedig ismét egy $0$ és $b$ közé eső egész. Jelölje $f\left(k\mathrm{,}y\right)$ a (1) feladat azon részfeladatának optimális célfüggvényértékét, amelyben csak az első $k$ változót vesszük figyelembe, a jobb oldal pedig $y$. Tehát $\begin{array}{c}{\displaystyle \begin{array}{cccccccccc}\hfill f\left(k\mathrm{,}y\right)\hfill & \hfill =\hfill & \hfill \underset{}{\overset{}{\text{max}}}\hfill & \hfill (c_1{x}_1\hfill & \hfill +\hfill & \hfill c_2{x}_2\hfill & \hfill +\hfill & \hfill \text{...}\hfill & \hfill +\hfill & \hfill c_k{x}_k)\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill a_1{x}_1\hfill & \hfill +\hfill & \hfill a_2{x}_2\hfill & \hfill +\hfill & \hfill \text{...}\hfill & \hfill +\hfill & \hfill a_k{x}_k\hfill & \hfill \le \hfill & \hfill y\hfill \\ \multicolumn{12}{c}{\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow></math>}\mathrm{,}\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mn>2</mn></mrow></msub></mrow></math>}\mathrm{,}\text{...}\mathrm{,}\text{<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow><mi>x</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow></math>=0}vagy1.}\end{array}}\end{array}$ (12) Az első észrevétel, amit tehetünk, hogy az $f\left(\mathrm{1,}y\right)$ függvényt könnyű meghatározni, hiszen $\begin{array}{c}{\displaystyle \begin{array}{ccc}\hfill f\left(\mathrm{1,}y\right)\hfill & \hfill =\hfill & \hfill \underset{}{\overset{}{\text{max}}}{c}_1{x}_1\hfill \\ \hfill a_1{x}_1\hfill & \hfill =\hfill & \hfill y\hfill \\ \hfill x_1\hfill & \hfill =\hfill & \hfill 0\text{ vagy }1.\hfill \end{array}}\end{array}$ (13) A célfüggvény monoton növő az egyetlen $x_1$ változóban, így ezt olyan nagynak kell megválasztani, amilyen nagynak csak lehet, azaz a változó optimális értéke, $x_1^{*}$, pontosan akkor $1$, ha $a_1\le y$, különben pedig $0$. Eszerint $\begin{array}{c}{\displaystyle f\left(\mathrm{1,}y\right)=\{{\displaystyle \begin{array}{cc}\hfill {\displaystyle \mathrm{0,}}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo stretchy="false"><</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow></math>}}\hfill \\ \multicolumn{2}{c}{\text{<div style="line-height: 3pt"> </div>}}\\ \hfill {\displaystyle c_1}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo>≥</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mn>1</mn></mrow></msub></mrow></math>.}}\hfill \end{array}}}\end{array}$ (14) Tegyük fel most már, hogy az $f\left(k\mathrm{,}y\right)$ függvény értékét valamely rögzített $k$ mellett valamennyi $y$-ra ismerjük. Próbáljuk meghatározni az $f$ függvény értékeit, ha az első változója éppen $k+1$. A $k+1$ indexű tárgyat csak akkor lehet betenni a hátizsákba, ha a még felhasználható súlykorlát, $y$ legalább akkora, mint a tárgy súlya, azaz $a_{k+1}$. Ha ez nem teljesül, akkor az első $k$ tárggyal pontosan akkora érték érhető el, mint az első $k+1$ tárggyal. Ha viszont a feltétel teljesül, akkor mindkét lehetőséget, nevezetesen a tárgy elvitelét és otthon hagyását is számba kell venni. Tehát $\begin{array}{c}{\displaystyle f\left(k+\mathrm{1,}y\right)=\{{\displaystyle \begin{array}{cc}\hfill {\displaystyle f\left(k\mathrm{,}y\right)\mathrm{,}}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo stretchy="false"><</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math>}}\hfill \\ \hfill {\displaystyle \underset{}{\overset{}{\text{max}}}\left\{f\left(k\mathrm{,}y\right)\mathrm{,}f\left(k\mathrm{,}y-a_{k+1}\right)+c_{k+1}\right\}\mathrm{,}}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo>≥</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math>.}}\hfill \end{array}}}\end{array}$ (15) Ismét megállapítható, hogy az $f\left(\mathrm{1,}y\right)$ ($y=0$, $\text{...}$, $b$) értékek ismeretében az $f\left(k\mathrm{,}y\right)$ ($y=0$, $\text{...}$, $b$) értékek egyszerűen számíthatók $k=2$, $\text{...}$, $n$ esetén, $k$ értékeinek növekvő sorrendjében. Tehát a (12) és (13) képletek a hátizsák feladat egy megoldási módszerét adják. Az $f\left(k\mathrm{,}y\right)$ érték meghatározásához legfeljebb 2 összehasonlításra és egy összeadásra van szükség. Ha csak az eredetileg kitűzött hátizsák feladatot akarjuk megoldani, akkor az $f\left(k\mathrm{,}y\right)$ függvény értékeit elegendő csak $k=\mathrm{1,}\text{...}\mathrm{,}n-1$ mellett meghatározni, valamint külön az $f\left(n\mathrm{,}b\right)$ értéket. Tehát $2nb-2b+2n$, illetve $nb-b+n$ felső korlát a szükséges összehasonlítások, illetve összeadások számára. Ha azonban kiváncsiak vagyunk arra, hogy a súlykorlát hogyan befolyásolja az optimális megoldást, akkor valamennyi $y$ mellett meg kell határozni $f\left(n\mathrm{,}y\right)$-t is. Tehát az utóbbi esetben az eljárás egyszeri végrehajtásával $b+1$ különböző jobb oldalra tudjuk a feladatot megoldani. Amíg tehát a műveletek nagyságrendje azonos a pénzváltási probléma megoldásához szükséges műveletekével, addig más a helyzet a szükséges memóriával. Az előző feladatnál mindössze két $b+1$ hosszú vektorra volt szükségünk, egy az $f$ függvény, egy pedig az optimális megoldást leíró $h$ vektor számára. Mostani feladatunknál azonban több memóriára van szükség. Első ránézésre az $f$ függvény tárolása egy $n\times \left(b+1\right)$ méretű tömböt igényel. Azonban vegyük észre, hogy az $f\left(k+\mathrm{1,}\mathrm{.}\right)$ függvény értékeinek meghatározásakor mindig csak az $f\left(k\mathrm{,}\mathrm{.}\right)$ függvény értékeit használjuk, és az $f\left(\mathrm{1,}\mathrm{.}\right)$, $\text{...}$, $f\left(k-\mathrm{1,}\mathrm{.}\right)$ függvények értékei soha többet nem jönnek elő. Tehát úgy járhatunk el, hogy először kiszámítjuk $f\left(\mathrm{1,}\mathrm{.}\right)$-et, majd ebből $f\left(\mathrm{2,}\mathrm{.}\right)$-t. Ezután már $f\left(\mathrm{1,}\mathrm{.}\right)$-re nincs szükségünk, tehát ennek a helyét használhatjuk $f\left(\mathrm{3,}\mathrm{.}\right)$ meghatározásához, ezután $f\left(\mathrm{2,}\mathrm{.}\right)$ helyét $f\left(\mathrm{4,}\mathrm{.}\right)$-hez, és így tovább. Tehát az $f$ függvényhez összesen két $b+1$ tömbre van szükség. Nem így az optimális megoldás tárolásához, ahol valóban kell az $n\times \left(b+1\right)$ méretű tömb. Jelölje $x^{*}\left(k\mathrm{,}y\right)$ az optimális megoldást, ami persze szintén függvénye a változók számának és a jobb oldalnak. Ekkor a (15) képletből adódóan $\begin{array}{c}{\displaystyle x^{*}\left(k+\mathrm{1,}y\right)=\{{\displaystyle \begin{array}{cc}\hfill {\displaystyle \mathrm{0,}}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo stretchy="false"><</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math>}}\hfill \\ \multicolumn{2}{c}{\text{<div style="line-height: 3pt"> </div>}}\\ \hfill {\displaystyle \mathrm{0,}}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo>≥</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math> és <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi><mrow><mo fence="true" stretchy="true">(</mo><mrow><mi>k</mi><mn>,</mn><mi>y</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow><mo stretchy="false">></mo><mi>f</mi><mrow><mo fence="true" stretchy="true">(</mo><mrow><mi>k</mi><mn>,</mn><mi>y</mi><mo stretchy="false">-</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></mrow><mo fence="true" stretchy="true">)</mo></mrow><mo stretchy="false">+</mo><mrow><msub><mrow><mi>c</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math>}}\hfill \\ \multicolumn{2}{c}{\text{<div style="line-height: 3pt"> </div>}}\\ \hfill {\displaystyle \mathrm{1,}}& {\displaystyle \text{ha <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo>≥</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math> és <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi><mrow><mo fence="true" stretchy="true">(</mo><mrow><mi>k</mi><mn>,</mn><mi>y</mi></mrow><mo fence="true" stretchy="true">)</mo></mrow><mo>≤</mo><mi>f</mi><mrow><mo fence="true" stretchy="true">(</mo><mrow><mi>k</mi><mn>,</mn><mi>y</mi><mo stretchy="false">-</mo><mrow><msub><mrow><mi>a</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></mrow><mo fence="true" stretchy="true">)</mo></mrow><mo stretchy="false">+</mo><mrow><msub><mrow><mi>c</mi></mrow><mrow><mi>k</mi><mo stretchy="false">+</mo><mn>1</mn></mrow></msub></mrow></math>.}}\hfill \end{array}}}\end{array}$ (16) Ekkor a tényleges ${\text{x}}^{*}$ optimális megoldást úgy kapjuk, hogy először eldöntjük $x_n$ értékét, ami természetesen az $\begin{array}{c}{\displaystyle x_n^{*}=x^{*}\left(n\mathrm{,}b\right)}\end{array}$ egyenlet alapján történik. Ezután döntünk $x_{n-1}$ felől $\begin{array}{c}{\displaystyle x_{n-1}^{*}=x^{*}\left(n-\mathrm{1,}b-a_n{x}_n^{*}\right)}\end{array}$ szerint, és így folytatjuk, míg végül az $\begin{array}{c}{\displaystyle x_1^{*}=x^{*}\left(\mathrm{1,}b-a_2{x}_2^{*}-\text{...}-a_n{x}_n^{*}\right)}\end{array}$ teljes megoldást meghatároztuk. Tehát legalább $\left(n+1\right)\times \left(b+1\right)$ méretű memóriára van szükségünk. Ha nem egy feltételünk volna, hanem több, például a turista nemcsak az elviendő tárgyak súlyát, hanem térfogatát is korlátozná, akkor a memória igény és persze vele együtt a számítási igény is megsokszorozódna, ezért ekkor már más megoldási módszereket kellene használni.   Vizvári Béla, Budapest, ELTE ${}^{*}$${}^1$ ${}^{*}$${}^2$