[es] - Problem ranca(Knapsack problem)

Krejmer
Stefan Savić
Učenik
Rep Srpska,Gradiška

Član broj: 200438
Poruke: 19
*.teol.net.

Sajt: www.google.rs

Profil

^{20.05.2010. u 14:53 - pre 169 meseci}

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.

Odgovor na temu

savkic
Igor Savkić

Moderator
Član broj: 92186
Poruke: 2739

+92 Profil

Re: Problem ranca(Knapsack problem)

^{20.05.2010. u 18:45 - pre 169 meseci}

> 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

Do not be a help vampire (http://slash7.com/pages/vampires), use the google.

How to ask questions the smart way:
http://www.catb.org/~esr/faqs/smart-questions.html
http://solair.eunet.rs/~fangor...stions/smart-questions.sr.html

Odgovor na temu

Krejmer
Stefan Savić
Učenik
Rep Srpska,Gradiška

Član broj: 200438
Poruke: 19
*.teol.net.

Sajt: www.google.rs

Profil

Re: Problem ranca(Knapsack problem)

^{20.05.2010. u 20:23 - pre 169 meseci}

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. ;)

Odgovor na temu

Krejmer
Stefan Savić
Učenik
Rep Srpska,Gradiška

Član broj: 200438
Poruke: 19
*.teol.net.

Sajt: www.google.rs

Profil

Re: Problem ranca(Knapsack problem)

^{26.05.2010. u 20:19 - pre 169 meseci}

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.

Odgovor na temu

Nikolavlasotince
Nikola Stojiljkovic
Vlasotince/Beograd

Član broj: 139391
Poruke: 109
*.ADSL.neobee.net.

+1 Profil

Re: Problem ranca(Knapsack problem)

^{29.05.2010. u 22:54 - pre 169 meseci}

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...

Odgovor na temu