[amartinez---FDasf]

Eso está en el link
https://drive.google.com/drive/folders/1ZVxtewUs-3vPB9Pibdtpf2NYjo1hnEZY

[Richard R Richard]

Siempre es bueno recordar el enunciado.

Dado un conjunto de \(n\) elementos o artículos numerados del \(1\) al \(n\): [1] )
• Cada elemento \(i\) (con \(1 \le i \le n\)) tiene asociado un peso \(w_i > 0\) y un valor (o beneficio) \(v_i > 0\).
• Se dispone de una mochila con una capacidad máxima de peso \(W > 0\).
• La condición 0-1 significa que cada objeto es indivisible: o se incluye por completo en la mochila (\(x_i = 1\)) o se deja fuera (\(x_i = 0\)), sin poder tomar fracciones de él.


Encontrar el subconjunto de elementos que maximice la suma de sus valores, de tal manera que la suma de sus pesos no exceda la capacidad \(W\) de la mochila. )

Formulación matemática

\(\text{Maximizar}\quad \sum _{i=1}^{n}v_{i}x_{i}\)
\(\text{Sujeto\ a:}\quad \sum _{i=1}^{n}w_{i}x_{i}\le W\)
\(x_{i}\in \{0,1\}\quad \forall i\in \{1,2,\dots ,n\}\)
• \(x_i = 1\): el objeto \(i\) se incluye en la mochila.
• \(x_i = 0\): el objeto \(i\) se excluye.
 

Ahora sí, yo lo recordaba con otro relato para llegar al mismo planteo, es un NP completo. Espero tengas buena devolución en lo que propones.

[Richard R Richard]

Y bueno si quitas lo que has hecho de la nube ,pasan cuatro cosas,

• parece que estas apurado y no das tiempo a contestar,
• ahora ya nadie te podrá ayudar,
• los que se habían dispuesto , no tienen forma de cotejar nada respecto a tu propuesta y perdieron el tiempo.
• y creo infringes las normas del foro, al quitar información útil.

Por otra parte mi idea era comparar soluciones con otro algoritmo mio, luego tamaños de archivo, memoria tiempo de resolución etc. Bueno  , nada, aire, ahora.

Pero suerte logre copiar los datos  de tu ejemplo

Código: [Seleccionar]


lista_objetos = [
    ("A", 10, 60), 
    ("B", 20, 100),
    ("C", 30, 120), 
    ("D", 5, 24), 
    ("E", 5, 24), 
    ("F", 6, 25), 
    ("G", 7, 26), 
    ("H", 8, 28), 
    ("I", 9, 30), 
    ("J", 10, 31), 
    ("K", 11, 32), 
    ("L", 12, 33), 
    ("M", 13, 34), 
    ("N", 14, 35), 
    ("O", 15, 36), 
    ("P", 16, 37), 
    ("Q", 17, 38), 
    ("R", 18, 39), 
    ("S", 19, 40), 
    ("T", 20, 41) 
]Mis resultados para ese ejemplo

cnt obj = 20
objetivo peso max= 50
Solución
obj , A , B , D , E , F suma: 233 peso: 46

Aver si alguien lo mejora .

Saludos

[amartinez---FDasf]

La verdad le erré mal, disculpen por hacerles perder el tiempo. No sabia que se necesitaba crear matemática nueva para resolver los problemas np y que tiene que haber contenido más formal.

Sin embargo, he seguido trabajando en esto, creando definiciones inductivas matematicas sobre tablas de valuación y una partición especifica me quedó ordenada por un truquito en el paso base de la inducción y he hecho otra publicación pero para el problema subset sum que es mas simple que este.

He hecho muchas pruebas antes para no hacerles perder tiempo y me quedo algo polinomial esta vez. Puse el codigo directo para que no tengan que perder tiempo leyendo.

Gracias por su tiempo y ojalá algun dia se pueda resolver este problema.