Pripreme za algoritme(11)

Problem naprtnjače (problem ruksaka, eng. knapsack problem) je problem kombinatorne optimizacije. Na danom skupu predmeta od kojih su za svaki predmet zadane težina i korisnost, potrebno je odrediti koliko predmeta stane u naprtnjaču fiksnog kapaciteta tako da je ukupna korisnost što veća i da je ukupna težina predmeta u naprtnjači manja ili jednaka kapacitetu naprtnjače. Problem naprtnjače često se susreće u kombinatorici, teoriji kompleksnosti, kriptografiji i primijenjenoj matematici.
Primjer zadatka: Torba, IBT 2008
-------------------------------------------------------------------------------------------------------------------
Martina je potajno napustila teško natjecanje iz informatike pola sata prije završetka, kako bi mogla potamaniti što više čokolada koje se dijele natjecateljima, po mogućnosti prije nego Ivana učini to isto. Nakon što je pojela sve što je mogla, odlučila je što više tih čokolada ponijeti kući. Na prethodnom kolu natjecanja saznala je da njena torba može izdržati masu od najviše N grama.
Kako je preostalo M čokolada, a na svakoj čokoladi piše njena masa izražena u gramima,moguće je odrediti koliko maksimalno čokolade Martina može odnijeti u svojoj torbi. Napišite program koji to određuje.
Važno: Martina mora uzimati isključivo cijele čokolade, tj. ne smije ih lomiti.
-------------------------------------------------------------------------------------------------------------------

Uzmite za svaki predmet njegovu vrijednost i podjelite ju sa velicinom da dobijete odnos vrijednost/velicina, i nakon toga uzimite samo one predmete koji imaju najveci omjer.
Dakle sortirate te predmete po omjeru vrijednosti, krenete od onoga koji ima najveći omjer, provjerite stane li u ruksak, ako ne stane idete na idući po vrijednosti, ako on stane u ruksak, oduzimate njegovu velicinu od velicine ruksaka da dobijete slobodno preostalo mjesto u ruksaku. Pa opet iznova trazite predmet sa najvecim omjerom koji stane u preostalo mjesto ruksaka, to ponavljate dokle god ima mjesta i predmeta koji bi mogli stati.

Rješenje:
------------------------------------------------------------------------------------------------------------------
const MAXM = 15;
var n, m, i, najvise, masa : integer;
    g : array[1..MAXM] of integer;
    (*  p(i) = 0 ako i-tu cokoladu ne uzimamo
    p(i) = 1 ako i-tu cokoladu uzimamo
    p(0) ima posebnu namjenu: ako je algoritam zavrsio, bit ce p(0) = 1 *)
    p : array[0..MAXM] of integer;
    begin
    readln(n);
    readln(m);
    for i:=1 to m do readln(g[i]);
    for i:=0 to m do p[i] := 0;
    najvise := 0;
    repeat
        masa := 0;
        for i:=1 to m do if p[i] = 1 then masa := masa + g[i];       
        if (masa <= n) and (masa > najvise) then najvise := masa;
    p[m] := p[m] + 1;
        i := m;
        while (p[i] > 1) do
        begin
            p[i] := 0;
            i := i - 1;
            p[i] := p[i] + 1;
        end;
    until p[0] <> 0;
    writeln(najvise);
end.
---------------------------------------------------------------------------------------------------------------
Problem naprtnjače je jedan od jednostavnijih primjera dinamičkoga programiranja, tako je današnja lekcija bila uvertira za sljedeće.