infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Sorin Rita din Martie 14, 2011, 16:34:12

Titlul: dinamica
Scris de: Sorin Rita din Martie 14, 2011, 16:34:12

Am o problema. Cred ca se rezolva prin programare dinamica si nu stiu de ce dar am impresia ca are legatura cu problema rucsacului. Insa nu imi pot da seama. Ideea e ca am un vector cu numere,nu neaparat distincte, si trebuie sa determin cea mai mare suma care se poate forma din elementele vectorului mai mica sau egala cu o valoare s. Cum pot face asta ?

Titlul: RÄƒspuns: dinamica
Scris de: FMI Romila Remus Arthur din Martie 14, 2011, 16:49:48

Faci exact ca la rucscac iar la final in loc sa te intrebi daca suma S a fost formata pui un while si afli cea mai mare suma mai mica decat S formata.

Cod:

while(!format[--S]);
cout<<S;

Titlul: RÄƒspuns: dinamica
Scris de: Sorin Rita din Martie 14, 2011, 18:00:44

mdea..tot nu reusesc...ideea e ca nu prea inteleg o chestie..
la problema rucsacului am si greutatea si un cost...ori aici costul ala nu il am.

imi poti explica putin algoritmul ?

Titlul: RÄƒspuns: dinamica
Scris de: FMI Romila Remus Arthur din Martie 14, 2011, 18:12:04

Cod:

maxim = 0;//suma maxima pe care am format-o
format[0]=1;
for(i=1;i<=N;i++)
{
    in>>nr;
    for(j=maxim;j>=0;j--)
        if(format[j])  //daca am format deja suma j
            format[nr+j]=1;  //marchez suma j+nr ca fiind formata
    if(maxim<=S)maxim+=nr;  //actualizez suma maxima.daca este mai mare decat S nu are rost sa o mai actualizez
}

Pentru fiecare suma deja formata aduni valoarea citita formand astfel noi sume.

Titlul: RÄƒspuns: dinamica
Scris de: Sorin Rita din Martie 14, 2011, 18:42:50

Iti multumesc. In sfarsit am inteles. :ok: