Problema Problema rucsaculuirucsacului

( cazul continuu)( cazul continuu)

Elev: Pop VladElev: Pop Vlad

Cls a XI-a BCls a XI-a B

EnunţulEnunţul problemei problemei

O persoană are un rucsac cu ajutorul căruia poate O persoană are un rucsac cu ajutorul căruia poate

transporta o greutate maximă transporta o greutate maximă G.G. Persoana are la Persoana are la

dispoziţie dispoziţie nn obiecte şi cunoaşte pentru fiecare obiect obiecte şi cunoaşte pentru fiecare obiect greutatea şi câştigul care se obţtine în urma transportului greutatea şi câştigul care se obţtine în urma transportului său la destinaţie.său la destinaţie.

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

ExempluExemplu

CCâştigâştig

GreutatGreutatee

EficienţEficienţăăCâştigCâştig

EficienţăEficienţă

EficienţEficienţăă

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

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

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

şi se preiau în calcul în această ordineşi se preiau în calcul în această ordinePas 3. Câştigul iniţial va fi 0 iar greutatea rămasă de încărcat va fi G.Pas 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 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:au fost luate în considerare toate obiectele se procedează astfel: - dintre obiectele neîncărcate se selectează acela cu cea mai ăridicată - dintre obiectele neîncărcate se selectează acela cu cea mai ăridicată

eficienţă de trasnport şi avem două posibilităţi:eficienţă de trasnport şi avem două posibilităţi: a) obiectul încape in totalitate în rucsac deci se scade din greutatea 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 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 datorat transportului acestui obiect, se tipăreşte 1 dacă întreg obiectul a fost încărcat.încărcat.

b) obiectul nu încape în totalitate în rucsac caz în care se calculează ce 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 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 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. obiect iar greutatea rămasă de încărcat devine 0.

ImplementareImplementare

Obiect= obiectele ce se introdu Obiect= obiectele ce se introdu în rucsac şi care în rucsac şi care sunt caracterizate sunt caracterizate prin cost(c), prin cost(c), greutate(Go), eficienta(e);greutate(Go), eficienta(e);

G= greutatea maximă ce se poate introduce în G= greutatea maximă ce se poate introduce în rucsac;rucsac;

Ct= câştigul total ce se obţine în urma Ct= câştigul total ce se obţine în urma transportului obiectelor;transportului obiectelor;

P= procentul care se calculează când obiectul nu P= procentul care se calculează când obiectul nu se poate introduce în rucsac;se poate introduce în rucsac;

Program rucsac;Program rucsac;Type obiect=recordType obiect=record C,Go,E:real;C,Go,E:real; endend;;

var ok:boolean;var ok:boolean;v:array[1..100] of obiect;v:array[1..100] of obiect;

aux:obiect;aux:obiect; i,n,t:integer;i,n,t:integer; G, ct:real;G, ct:real;

BeginBeginwrite(‘n=‘); readln(n);write(‘n=‘); readln(n);write(‘G=‘); readln(G);write(‘G=‘); readln(G); For i:=1 to n do BeginFor i:=1 to n do Begin write(‘castigul pentru obiectul’, i);write(‘castigul pentru obiectul’, i); readln(v[i].c);readln(v[i].c); write(‘greutatea obiectului ‘,i);write(‘greutatea obiectului ‘,i); readln(v[i].Go);readln(v[i].Go);v[i].e:=v[i].c/v[i].Go;v[i].e:=v[i].c/v[i].Go; End;End;t:=1;t:=1; RepeatRepeat ok:=true;ok:=true; for i:=1 to n-t dofor i:=1 to n-t do if v[i].e<v[i+1].e then Beginif v[i].e<v[i+1].e then Begin ok:=false;ok:=false;

aux:=v[i];aux:=v[i]; v[i]:=v[i+1];v[i]:=v[i+1];v[i+1]:=aux;v[i+1]:=aux; end;end; t:=t+1;t:=t+1; until ok;until ok;i:=1; ct:=0;i:=1; ct:=0;while (G<>0) and (i<=n) do Beginwhile (G<>0) and (i<=n) do Begin if v[i].Go<G then Beginif v[i].Go<G then Begin ct:=ct+v[i].c;ct:=ct+v[i].c; G:=G-v[i].Go;G:=G-v[i].Go;writeln(‘obiectul’,I,’1’);writeln(‘obiectul’,I,’1’);

endendelse beginelse begin

P:=G*100/v[i].c*p)/100;P:=G*100/v[i].c*p)/100;writeln(‘obiectul,I,se introduce in procent de ‘,P);writeln(‘obiectul,I,se introduce in procent de ‘,P);

end;end;i:=i+1;i:=i+1;

end;end;writeln(‘castigul total este ‘,ct);writeln(‘castigul total este ‘,ct);

end;end;readln;readln;End.End.