Knapsack help

[•SpiderMan]

Imi poate arata si mie de exemplu daca am N valori si vreau sa vad daca X se poate obtine adunand acele valori, cu algoritmul knapsack? Multumesc anticipat .

[•popoiu.george]

Sunt 2 cazuri : cand poti aduna de mai multe ori aceeasi valoare si cand poti aduna fiecare valoare o singura data.

Care te intereseaza ?

[•SpiderMan]

Aici e problema .

[•popoiu.george]

Citeste articolul cu solutii. O sa vezi ca nu e nevoie de Knapsack.

http://infoarena.ro/preoni-2008/runda-1/solutii#economie

[•SpiderMan]

Am citit, dar nu stiu sigur, adica sa zicem pentru exemplul asta :

Cod:

3
2
3
5

Dau de 2, si ce fac, adica il bag intr-un vector si ce marchez ? Asta nu inteleg :-"

[•dornescuvlad]

Din - vector in care tii 1, daca poti forma suma i si 0 daca n-o poti forma.

Cod:

Din[0] = 1 //e clar
for(i=1;i<=n;i++)
    if(Din[V[i]]==0) 
       {
            sol[++nrSol]=V[i]; //bagi in solutie daca nu se poate forma suma V[i]
            for(j=0;j<=V[n];j++) //cauti crescator sumele pe care le poti forma cu V[i] 
            //pentru ca poti folosi o moneda de mai multe ori
                    if(Din[j] && j+V[i]<=V[n]) //pana nu depasesti valoarea maxima a monedelor
                                 Din[j+V[i]]=1; //le marchezi 
       }