Elev: Ninacs MarianElev: Ninacs Marian

Cls a XI-a BCls a XI-a B

EnunţulEnunţul problemei problemei

O persoană are un rucsac cu ajutorul căruia poate transporta o greutate maximă G. Persoana are la dispoziţie n obiecte şi cunoaşte pentru fiecare obiect greutatea şi câştigul care se obţine în urma transportului său la destinaţie.

Se cere să se precizeze ce obiecte trebuie să transporte persoana în aşa fel încât câştigul să fie maxim.

Obiectele pot fi tăiate pentru transportul la destinaţie.

CCââştigtig

GreutaGreutatete

EficienEficienţăţăCâCâştigtig

EficienEficienţăţă

EficienEficienţăţă

5

1

10

3

3

2 4

15

6

6

2

7

5:1=

10:3=

7:2=

3:4=

15:6=

6:2=

5 3.33

3.5 0.75

2.5

3

G=4 kg

C=3

E=0.75

G=6 kg

C=15

E=2.5

G=3 kg

C=10

E=3.33

G=2 kg

C=6

E=3

G=2 kg

C=7

E=3.5

G=1 kg

C=5

E=5

În valiză mai încap:15 kg

cu un câştig total de:

0 Ron

14 kg

5 Ron

12 kg

12 Ron

9 kg

22 Ron

7 kg

28 Ron

1 Kg

43 Ron

25% din obiect

43.75 Ron

AlgoritmulPas 1. Se calculează pentru fiecare obiect în parte eficienţa de transport

rezultată prin împărţirea câştigului la greutate.Pas 2. Obiectele se sortează în ordine descrescătoare a eficienţei de transport şi

se iau în calcul în această ordinePas 3. Câştigul iniţial va fi 0 iar greutatea rămasă de încărcat va fi G.Pas 4. Atât timp cât nu a fost completată greutatea maxima a rucsacului şi nu

au fost luate în considerare toate obiectele se procedează astfel: - dintre obiectele neîncărcate se selectează acela cu cea mai ridicată

eficienţă de transport şi avem două posibilităţi: a) obiectul încape in totalitate în rucsac deci se scade din greutatea rămasă

de încărcat, greutatea obiectului iar la câştig se cumulează câştigul datorat transportului acestui obiect, se tipăreşte 1 dacă întreg obiectul a fost încărcat.

b) obiectul nu încape în totalitate în rucsac caz în care se calculează ce parte din el poate fi transportată, se cumulează câştigul obţinut cu transportul acestei părţi şi se tipăreşte procentul care s-a încărcat din obiect iar greutatea rămasă de încărcat devine 0.

Program rucsac;Type vector =array[1..9] of real; var c,g,ef:vector; n,I,man1:integer;

inv:boolean; gv,man,castig:real;

ordine: array[1..9] of integer; Beginwrite(‘n=‘); readln(n);write(‘gv=‘); readln(gv); For i:=1 to n do Begin write(‘c[‘, i,’]=‘); readln(c[i]); write(‘g[‘,i,’]=‘);readln(g[i]); ordine[i]:=i; ef[i]:+c[i]/g[i] end;Repeat inv:=false; for i:=1 to n-1 do if e[i]<ef[i+1] then Begin

man:=ef[i]; ef[i]:=ef[i+1]; ef[i+1]:=man;man:=c[i]; c[i]:=c[i+1]; c[i+1]:=man;man:=g[i]; g[i]:=g[i+1]; g[i+1]:=man;inv:=true;man1:=ordine[i]; ordine[i]:=ordine[i+1]; ordine[i+1]:=man1;

end; until not inv;castig:=0;i:=1;while (gv>0) and (i<=n) do begin if gv>g[i] then begin writeln (‘obiectul ’ ,ordine[i],’ ‘,1);gv:=gv-g[i];castig:=castig+c[i];

end else begin writeln (‘obiectul ‘,ordine[i],’ ‘gv(g[i]:1:2); castig:=castig+c[i]*gv/g[i]; gv:=0; i:=i+1; end;writeln(‘castig total=‘,castig:3:2);readln;end.