{pseudokod algoritmu pro reseni problemu batohu s celociselnym zadanim to, ze zadani je celociselne je podstatne !!!! } {vstup} const M = 17; {velikost batohu} N = 5; {pocet typu zbozi} var vel : array[1..N] of integer; {vel[j] je velikost j-teho typu zbozi} {predpokladame, ze pole vel je neklesajici} hod : array[1..N] of integer; {hod[j] je hodnota j-teho typu zbozi} {pomocne datove struktury} zisk : array[1..M] of integer; {zisk[i] je maximalni mozna hodnota batohu velikosti i} best : array[1..M] of 0..N; {best[i] je index typu posledniho kusu zbozi, ktere bylo do optimalniho batohu velikosti i vlozeno} {inicializace} for i:=1 to M do begin best[i]:=0; zisk[i]:=0; end; {vypocet} for j:=1 to N do {vnejsi cyklus pres typy zbozi} begin for I:= 1 to M do {vnitri cyklus pres velikost batohu} begin if i>= vel[j] then {j-te zbozi se vejde do batohu} begin nz:= zisk[i-vel[j]]+hod[j]; {nz je max. zisk kdyz do batohu velikosti i vlozime j-te zbozi } if zisk[i] < nz then {vyplatise dat do batohu zbozi typu j} begin {aktualizace} zisk[i]:= nz; {novy max. zisk} best[i]:=j; {dosahli jsme ho vlozenim j-teho zbozi} end; end; end; {rekonstrukce optimalniho batohu velikosti i} writeln('optimalni obsah batohu velikosti', i:3, ' ma hodnotu', zisk[i]:4, 'a sklada se ze zbozi typu:'); j:=i; while zisk[j]>0 do begin write(best[j]:3); j:= j - vel[best[j]]; {po vyjmuti zbozi best[j] zbyva volneho mista} end;