Problem ranca(Knapsack problem)

[ Krejmer @ 20.05.2010. 14:53 ] @

Ljudi treba mi pomoć oko ovog algoritma,ne mogu da ga shvatim baš najbolje,ustvari ne mogu ni da nađem kod na internetu u Pascalu.

Nešto sam probao,ali ne ide.Inače ovo sam radio na principu jednog pseudokoda,ali izgleda da ga nisam dobro shvatio.(ili čak to nije možda ni tačno).

E sad,ovaj kod ne da je spor,nego nekad ni neće najjednostavniji primjer da uradi.

Code:
program knepsek;
type
ObicniNiz=array[1..100] of integer;
var
v,z:ObicniNiz;
M:ObicniNiz;
n,i,j,k,W:integer;
max:integer;
begin
readln(W,n);   //W je zapremina ranca,n je broj predmeta
//unosenje vrijednosti
for i:=1 to n do
   begin
   readln(z[i],v[i]);        //z je zapremina i-tog predmeta,v je vrijednost
   end;
//glavni dio
for j:=1 to W do
begin
M[j]:=0;
k:=0;
for i:=1 to n do
begin
  for j:=w downto 1 do
  begin
   if M[j-z[i]]+v[i]>M[j] then
   M[j]:=M[j-z[i]]+v[i] ;
   if M[j]>max then
       max:=M[j];               //cuvam max
   end;
   end;
   end;
   writeln(max);
   readln;
   end.

[ savkic @ 20.05.2010. 18:45 ] @

> Ljudi treba mi pomoć oko ovog algoritma,ne mogu da ga shvatim baš najbolje,ustvari ne mogu ni da nađem kod na internetu u Pascalu.
> Nešto sam probao,ali ne ide.Inače ovo sam radio na principu jednog pseudokoda,ali izgleda da ga nisam dobro shvatio.(ili čak to nije možda ni tačno).
> E sad,ovaj kod ne da je spor,nego nekad ni neće najjednostavniji primjer da uradi.

Taj problem i jeste komplikovan, koliko vidim ima raznih algoritama, različite efikasnosti, ako taj koji imaš nije najbolji, potraži neki drugi. Pogledaj recimo ovaj link, ima pascal primer, verovatno se mogu i naći bolje varijante.

http://www.cs.sunysb.edu/~algo...mplement/syslo/implement.shtml

[ Krejmer @ 20.05.2010. 20:23 ] @

Dobra stranica.Mada nije ni ova loša.

http://ace.cs.ohiou.edu/~razvan/courses/cs404/lecture16.pdf

Pošto vidim da nigdje na forumu nema baš detaljno objašnjeno oko ovog problema,sutra očekujte tutorijal. ;)

[ Krejmer @ 26.05.2010. 20:19 ] @

Izvinjavam se,slabo imam slobodnog vremena,evo koda,objasniću princip neki drugi put,čim smognem vremena.
Dakle evo koda,nije teško razumjeti.
N-Broj predmeta
M-Zapremina ranca
Z-Zapremina(i-tog predmeta)
V-Vrijednost(i-tog predmeta)
B-Rezultni niz

Code:
program utovar1;
var
B:array[0..1000]of longint;
V,Z:array[1..10] of integer;
N, M, j, i: integer;
begin
  read(M,N);
   for i:=1 to M do
    begin
     read(Z[i])
    end;
   for i:=1 to M do
    begin
     read(V[i]);
    end;
    B[0]:=0;
    C[0]:=0;
     for j:=1 to N do
      begin
       B[j]:=0;
       C[j]:=0;
       for i:=1 to M do
       if Z[i]<=q then
       if B[j-Z[i]]+V[i]>B[j] then B[j]:=B[q-Z[i]]+V[i];
      end;
writeln(B[N]);
readln;
end.

[ Nikolavlasotince @ 29.05.2010. 22:54 ] @

Evo pokusacu ja da objasnim nesto ako mogu...

Dakle, knapsack problem se resava putem dinamickog programiranja. U ovom slucaju je B[k] najbolji nacin (najbolje resenje) na koji mozemo da popunimo ranac zapremine k. Mi popunjavamo svaki ranac zapremine 1 do M (i=1, M) redom... U trenutku kada popunjavamo ranac zapremine i, mi smo popunili sve ranceve zapremine 1 do (i-1) na optimalan nacin (najbolji moguci). Zatim proveravamo koliko bi bilo najbolje resenje ako bi u ranac zapremine i stavili j-ti predmet (proveravamo sve predmete j=1, N)...
j-ti predmet ima zapreminu Z[j] i vrednost V[j]. Da bi stavili predmet zapremine Z[j] potrebno je da imamo slobodnu Z[j] zapreminu u rancu... Sto znaci da mozemo da imamo najvise i-Z[j] "zapreminskih jedinca" popunjenih na optimalan nacin. Dakle, kad stavimo j-ti predmet zapremine Z[j] u ranac zapremine i, nama ostaje i-Z[j] zapreminskih jedinica da popunimo... Tu zapreminu smo ranije vec popunili na optimalan nacin i to je B[i-Z[j]]... Znaci najbolji nacin da popunimo ranac zapremine i a da j-ti predmet bude u njemu je B[i-Z[j]] + V[j]... Pronadjemo dakle za svaki predmet najbolje resenje (j=1, N) i to resenje zapamtimo u B... I na kraju je resenje B[M] (M - zapremina ranca)...
Pre nego sto pokusamo da stavimo j-ti predmet uvek proverimo da nije zapremina tog predmeta > zapremine ranca koji trenutno popunjavamo (jer ako bi bila veca predmet ne bi mogao da stane u ranac)...
Inicijalizacija je d[0] = 0; jer u ranac zapremine 0 ne mozemo da stavimo nijedan predmet...

@Krejmer
U tvom kodu gore umesto q treba da stoji j...