dinamica

[•soriyn]

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 ?

[•R.A.R]

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;

[•soriyn]

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 ?

[•R.A.R]

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.

[•soriyn]

Iti multumesc. In sfarsit am inteles.