Problema rucsacului( cazul continuu)

Elev: Pop VladCls a XI-a B

Enunul problemei

O persoan are un rucsac cu ajutorul cruia poate transporta o greutate maxim G. Persoana are la dispoziie n obiecte i cunoate pentru fiecare obiect greutatea i ctigul care se obtine n urma transportului su la destinaie. Se cere s se precizeze ce obiecte trebuie s transporte persoana n aa fel ncat ctigul s fie maxim.

Exemplu511033241566275:1=10:3=7:2=3:4=15:6=6:2=53.333.50.752.53

G=4 kgC=3E=0.75G=6 kgC=15E=2.5G=3 kgC=10E=3.33G=2 kgC=6E=3G=2 kgC=7E=3.5G=1 kgC=5E=5n valiz mai ncap:15 kgcu un ctig total de:0 Ron14 kg5 Ron12 kg12 Ron9 kg22 Ron7 kg28 Ron1 Kg43 Ron25% din obiect43.75 Ron

AlgoritmulPas 1. Se calculeaz pentru fiecare obiect n parte eficiena de transport rezultat prin mprirea la ctigului la greutate.Pas 2. Obiectele se sorteaz n ordine descresctoare a eficienei de transport i se preiau n calcul n aceast ordinePas 3. Ctigul iniial va fi 0 iar greutatea rmas de ncrcat va fi G.Pas 4. Att timp ct nu a fost completat greutatea maxima a rucsacului i nu au fost luate n considerare toate obiectele se procedeaz astfel: - dintre obiectele nencrcate se selecteaz acela cu cea mai ridicat eficien de trasnport i avem dou posibiliti: a) obiectul ncape in totalitate n rucsac deci se scade din greutatea rmas de ncrcat, greutatea obiectului iar la ctig se cumuleaz ctigul datorat transportului acestui obiect, se tiprete 1 dac ntreg obiectul a fost ncrcat. b) obiectul nu ncape n totalitate n rucsac caz n care se calculeaz ce parte din el poate fi transportat, se cumuleaz ctigul obinut cu transportul acestei pri i se tiprete procentul care s-a ncrcat din obiect iar greutatea rmas de ncrcat devine 0.

Implementare

Obiect= obiectele ce se introdu n rucsac i care sunt caracterizate prin cost(c), greutate(Go), eficienta(e);G= greutatea maxim ce se poate introduce n rucsac;Ct= ctigul total ce se obine n urma transportului obiectelor;P= procentul care se calculeaz cnd obiectul nu se poate introduce n rucsac;

Program rucsac;Type obiect=record C,Go,E:real; end;var ok:boolean;v:array[1..100] of obiect; aux:obiect; i,n,t:integer; G, ct:real;

Beginwrite(n=); readln(n);write(G=); readln(G); For i:=1 to n do Begin write(castigul pentru obiectul, i); readln(v[i].c); write(greutatea obiectului ,i); readln(v[i].Go);v[i].e:=v[i].c/v[i].Go; End;t:=1; Repeat ok:=true; for i:=1 to n-t do if v[i].e

aux:=v[i]; v[i]:=v[i+1];v[i+1]:=aux; end; t:=t+1; until ok;i:=1; ct:=0;while (G0) and (i