Problema de la mochila
MeT-X
21 de Julio del 2004
De antemano muchas gracias
a cualquiera que me pueda dar el codigo del problema de la mochila (backtracking)
a cualquiera que me pueda dar el codigo del problema de la mochila (backtracking)
WertMan
21 de Julio del 2004
Yo también estoy interesado en encontrar la solución para el problema de la mochila mediante el esquema divide y vencerás.
El problema de la mochila binaria consiste en lo siguiente:
Tenemos n objetos y una mochila. Cada objeto tiene un peso p y un valor v (siendo p y v enteros positivos). La mochila puede llevar un peso total que no sobrepase un valor P (en mi caso 2/3 del total de los pesos). Queremos llenar la mochila de tal forma que el valor de los objetos transportados sea máximo. Los objetos no se pueden fraccionar.
Pues bien, he encontrado soluciones a este problema con algoritmos voraces (greedy) y con programación dinámica, pero la estrategia divide y vencerás, al ser poco eficiente para este problema no la encuentro. Si alguien puede mandarme una solución, algo en pseudocódigo o código c++...
Gracias de antemano
El problema de la mochila binaria consiste en lo siguiente:
Tenemos n objetos y una mochila. Cada objeto tiene un peso p y un valor v (siendo p y v enteros positivos). La mochila puede llevar un peso total que no sobrepase un valor P (en mi caso 2/3 del total de los pesos). Queremos llenar la mochila de tal forma que el valor de los objetos transportados sea máximo. Los objetos no se pueden fraccionar.
Pues bien, he encontrado soluciones a este problema con algoritmos voraces (greedy) y con programación dinámica, pero la estrategia divide y vencerás, al ser poco eficiente para este problema no la encuentro. Si alguien puede mandarme una solución, algo en pseudocódigo o código c++...
Gracias de antemano
fdas
21 de Julio del 2004
Ten en cuenta que según muchos autores las técnicas de divide y vencerás son un subconjunto de las técnicas de programación dinámica
Quino3D
21 de Julio del 2004
funcion MochDyV(i,peso:N; var x:vector[n]de[0,1]):R
var global v:vector[n]:N; p:vector[n]:R;
S,N:R;
x1,x2:vector[n]de[0,1] fvar
si (i<1) entonces devuelve(0)
sino
si (p[i]>peso) entonces S=0
sino S=v[i]+ MochDyV(i-1,peso-p[i],x1)
finsi
N=MochDyV(i-1,peso,x2)
si (S>N) entonces
x=x1;x[i]=1;devuelve(S)
sino
x=x2;x[i]=0;devuelve(N)
finsi
finsi
fin
var global v:vector[n]:N; p:vector[n]:R;
S,N:R;
x1,x2:vector[n]de[0,1] fvar
si (i<1) entonces devuelve(0)
sino
si (p[i]>peso) entonces S=0
sino S=v[i]+ MochDyV(i-1,peso-p[i],x1)
finsi
N=MochDyV(i-1,peso,x2)
si (S>N) entonces
x=x1;x[i]=1;devuelve(S)
sino
x=x2;x[i]=0;devuelve(N)
finsi
finsi
fin
Quino3D
21 de Julio del 2004
Perdón, pero he intentado indentarlo con espacios pero no me lo acepta el foro. Este es el pseudocódigo que tengo en mis apuntes de DAA (Diseño y Análisis de Algoritmos) de la Universidad de Alicante. También tengo otros, si necesitaran de mi cualquier cosa más por favor remitanme un correo. Un saludo a todos.
darko
21 de Julio del 2004
Si ahora lo podeis poner para backtrakin' y algoritmos voraces pos ya de lujo.
Gracias
Gracias
roger
21 de Julio del 2004
Me harÃas un enorme favor si me hicieras llegar a mi también dicho codigo. gràcias!
pigma
21 de Julio del 2004
Quizá yo sea un completo ignorante al respecto, pero creo que tal vez puediese ayudarte alguien si escribieses el enunciado completo del problema en lugar de decir el problema de la mochila; que al menos yo no conozco por ese nombre.
Leonardo
21 de Julio del 2004
Dejame el enunciado del problema de la mochila e intentare realizar el codigo.
Gracias
Gracias
Vetro5
21 de Julio del 2004
No logro encontrar una solucion para resolverlo mediante divide y venceras, si alguien me lo puede mandar.Muchas gracias por todo
Natty
21 de Julio del 2004
Hola...quisiera saber si tienes la solución al Problema de la mochila (backtracking), en lenguaje C, si es asi serias tan amable de enviarmela...la necesito urgente...Gracias...!!!