Problema Rucsacului Problema Rucsacului

ElevElevăă :Reus Raluca :Reus Raluca

Se da un rucsac de capacitate,Se da un rucsac de capacitate,

volum si un numar de n obiecte volum si un numar de n obiecte specificandu-se volumul specificandu-se volumul obiectelor.Se cere un program obiectelor.Se cere un program care sa determine varianta de care sa determine varianta de introducere a obiectelor in introducere a obiectelor in rucsac astfel incat sa incapa cat rucsac astfel incat sa incapa cat mai multe obiecte.mai multe obiecte.

Exemplu Exemplu

N=5;

Volum=10kg;

Nr. obiectNr. obiect

GreutateGreutate2233 4455 7755

12 21 35 5343 4

Ob 1 Ob 2 Ob 3 Ob 4 Ob 5

Volumul disponibil al rucsacului este:

10 kg8 kg5 kg1 kg

Greutatea obiectului este prea mare

Algoritmul de rezolvare:Algoritmul de rezolvare: Pas1:Citirea volumelor fiecarui obiect şi a volumului Pas1:Citirea volumelor fiecarui obiect şi a volumului

rucsacului.rucsacului. Pas2:Iniţializăm obiectele.Pas2:Iniţializăm obiectele. Pas3:Se ordonează obiectele crescator in functie de Pas3:Se ordonează obiectele crescator in functie de

volumul lor.volumul lor. Pas4:Se inţializează volumul disponibil cu volumul Pas4:Se inţializează volumul disponibil cu volumul

obiectului.obiectului. Pas5:Se verifica dacă fiecare obiect incape in Pas5:Se verifica dacă fiecare obiect incape in

rucsac astfel:rucsac astfel: Daca volumul obiectului e mai mic sau egal Daca volumul obiectului e mai mic sau egal

decat volumul disponibil a rucsacului atunci decat volumul disponibil a rucsacului atunci acesta incape in rucsac si din volumul disponibil acesta incape in rucsac si din volumul disponibil a rucsacului scădem volumul obiectului.a rucsacului scădem volumul obiectului.

PasPas66:Dacă a rămas o zonă din rucsac neocupată :Dacă a rămas o zonă din rucsac neocupată atunci afişăm volumul rămas neocupat, în caz atunci afişăm volumul rămas neocupat, în caz contrar înseamnă că nu am putut introduce nici un contrar înseamnă că nu am putut introduce nici un obiect în rucsacobiect în rucsac

Implementare Implementare

max_ob –nr maxim de obicte care pot fi puse max_ob –nr maxim de obicte care pot fi puse in rucsacin rucsac

n-nr de obiecte.n-nr de obiecte.

v_dis-volumul disponibil din rucsac.v_dis-volumul disponibil din rucsac.

o-obiectele.o-obiectele.

Greutate-greutatea fiecarui obiect.Greutate-greutatea fiecarui obiect.

AlgoritmAlgoritmProgram rucsacProgram rucsac::Const max_ob =100;Const max_ob =100;Type vector=array [1..100] of integer ;Type vector=array [1..100] of integer ;Var volum,n,i:integer;Var volum,n,i:integer;greuate :array[1..max_ob] of integer;greuate :array[1..max_ob] of integer;Procedure citeste:Procedure citeste: BeginBeginRepeat (‘volumul rucsacului’);Repeat (‘volumul rucsacului’); readln(volum);readln(volum);Until volum>0;Until volum>0;Repeat Repeat write(‘nr.obiectelor’);readln(n);write(‘nr.obiectelor’);readln(n);Until (n>0) and (n<=max_ob);Until (n>0) and (n<=max_ob); For i:=1 to n doFor i:=1 to n doRepeat Repeat write(‘greutate[‘,I,’]=‘);write(‘greutate[‘,I,’]=‘); readln(greutate);readln(greutate);Until greutate[i]>0;Until greutate[i]>0; writeln;writeln;End;End;

Procedure rezolva;Procedure rezolva;Var a:array[1..ob_max] of integer;Var a:array[1..ob_max] of integer;V_dis,aux,i:integer;V_dis,aux,i:integer;Ok:boolean;Ok:boolean;BeginBeginFor i:1 to n do o[i]:=i;For i:1 to n do o[i]:=i; t:=1;t:=1;RepeatRepeat ok:=true;ok:=true;For i:=1 to n-t doFor i:=1 to n-t do If greutate[o[i]]>greutate[o[i]] thenIf greutate[o[i]]>greutate[o[i]] then beginbegin aux:=o[i];aux:=o[i]; o[i]:=o[i+1];o[i]:=o[i+1]; o[i+1]:=aux;o[i+1]:=aux; ok:=false;ok:=false; end;end; t:=t+1;t:=t+1;Until ok;Until ok;

Write(‘continutul posibil a rucsacului este’);Write(‘continutul posibil a rucsacului este’); v_dis:=volum;v_dis:=volum;For i:=1 to n doFor i:=1 to n do if greutate [o[i]]<=v_dis then beginif greutate [o[i]]<=v_dis then begin v_dis:=v_dis-greutate[o[i]];v_dis:=v_dis-greutate[o[i]]; writeln(‘obictul’,o[i],’de volum’,greutate[o[i]]);writeln(‘obictul’,o[i],’de volum’,greutate[o[i]]); end;end;If v_dis<volum thenIf v_dis<volum thenWriteln(‘volum ramas neocupat=‘,v_dis)Writeln(‘volum ramas neocupat=‘,v_dis) elseelseWriteln(‘nu incape nici un obiect in rucsac’);Writeln(‘nu incape nici un obiect in rucsac’);Writeln;Writeln;End;End;BeginBeginCiteste;Citeste;Rezolva;Rezolva;Readln;Readln;End.End.