Problema con algoritmo PD - Problema de la Mochi

Aziwar

Buenas! Tengo un problemilla con la programación dinámica y el problema de la mochila.

A la hora de elaborar la tabla, empieza haciéndola correctamente y derrepente llega a un punto en el que ya se empieza a hacer mal y no pillo el por qué.

El código para elaborar la tabla es el siguiente

spoiler



El último IF compara los casos en los que se introduce el elemento i en la mochila o no.

Por ejemplo para el ejemplo que estoy haciendo, el peso máximo sería 11 y el número de objetos 5 por lo que habrían 12 columnas (una es la primera todo 0 para poder determinar los elementos al final) y 5 filas. Pues me hace bien las 6 primeras columnas y después, las filas 1 y 2 que corresponderian a los objetos 1 y 2 se empiezan a hacer mal, pero sin embargo las 3,4 y 5 si salen bien... por eso es lo que me tiene extrañado.

A ver si alguien da con lo que falle pq yo no lo veo xD

Dod-Evers
spoiler

http://es.wikipedia.org/wiki/NP-completo

Aziwar

mmm no entiendo eso del NP Completo

bLaKnI

NP completitud en este caso? Quieres decir? Yo diria que es resoluble y que está en P, no?
Lo que pasa que existen las famosas tomas de decisión. Y estas variables son preconfigurables a voluntad de la empresa por ejemplo...

Qual es el problema de la mochila?
Es decir, se cual es pero en que ambito lo estas aplicando? Empresarial? Practica pura y dura?

Usuarios habituales

  • bLaKnI
  • Aziwar
  • Dod-Evers