Array
(
)

Programação Dinamica

Dioguito
   - 17 nov 2008

Alguem pode me ajudar . estou com um problema para desenvolver uma solução dinamica para akele problema da mochila booleana, onde um ladrão só tem uma mochila com uma capacidade x e tem q maximizar o valor dos produtos sem q os mesmo ultrapassem a capacidade da mochila , sendo q cada produto tem um peso agregado .

Eu tenho dois vetores um w(pesos dos produtos) e um v(valor dos produtos) e devo implementar uma solução dinamica para o problema seguindo esse portugol .. porém não consigo passar o mesmo para c ou c++ alguem pode me ajudar ?

mochila(w, v, n, W){
para Y = 0 até W faça
t[0, Y] = 0;

para i = 1 até n faça{
valorSem_i = t[i-1, Y]
se w[i] > Y então
valorCom_i = 0;
senão
valorCom_i = t[i-1, Y-w[i]] + v[i]
t[i, Y] = máximo(valorSem_i, valorCom_i)
}
}
Y=M

para i = n até 1 (decrescendo) faça
se t[i, Y] = t[i–1, Y] então
x[i] = 0;
senão
x[i] = 1
Y = Y – w[i]
retorne x