Proyecto 1 - Knapsack

Problema de la Mochila - Reporte de solución al algoritmos para generar el máximo de valores de un conjunto de productos de una mochila con capacidad limitada.

Desarrollo y lógica del problema

    Una solución al algoritmo sobre generar el máximo de valores de un conjunto de productos en una mochila con capacidad limitada puede resultar un tanto confuso, una forma para resolver el problema es mediante un árbol de decisiones, donde por ejemplo para un listado de 4 productos donde la capacidad de la mochila es de 936 tenemos la siguiente tabla.

Productos: 4

 Capacidad: 936

Producto    Valor       Volumen

1                  700             440

2                  258             117

3                  952             811

4                  993             491

    Necesitamos introducir un conjunto de productos que no sobrepasen la capacidad de la mochila y necesitamos saber cual es la mayor cantidad de valor que podemos recolectar. Una solución para esto es mediante el uso de un árbol de decisión por ejemplo a continuación:

    Entendemos que para cada nivel es un producto y que todos los nodos naranjados son los nodos que se permitieron entrar a la mochila, aquí el ganador es el camino que junte mas valor, por ejemplo: para la entrada anterior el resultado sería 1693 que nos indica la raya roja ganadora.

    El volumen del producto 1 y producto 4 no superan los 936 y la suma de sus valores superan cualquier otro.


    Otro ejemplo con un número de productos mas grande sería:

Productos: 8

Capacidad: 931

Producto       Valor       Volumen

1                   431           823

2                   590           359

3                   153           899

4                   370           292

5                   698           404

6                   876           699

7                   705           442

8                   527           757

    Aquí el resultado sería 1403 sumando los Productos 5 y 7.


Código y Pseudocódigo

cantidadProducto
cupoLimite
vectorValores[1000]
vectorEspacio[1000]

ganador = 0
producto = 0

procedimiento genera(espacio,valor,producto)
    //En este bloque paramos la búsqueda en el árbol
    si producto es igual a cantidadProducto entonces
        si ganador < valor entonces ganador <- valor
        regresa
    fin si
   
    //Si aun nos cabe el proximo producto creamos una rama con el valor positivo
    si espacio+vectorEspacio[producto] <= a cupoLimite entonces
        llama genera(espacio+vectorEspacio[producto],valor+vectorValor[producto],producto+1)
    fin si
   
    //Tambien creamos una rama en el arbol para que el producto no entre
    llama genera(espacio,valor,producto+1)
fin procedimiento


procedimiento main()

    lee cantidadProducto
    lee cupoLimite


    //Leemos los productos (su valor y espacio que ocupan)
    para i=0 hazta i<n haz i+1
        lee vectorValores[i]
        lee vectorEspacio[i]
    fin para
   
    //Generamos el arbol
     llama genera(0,0,0)

     imprime ganador

fin procedimiento

    A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.

http://groups.google.com/group/algcomp/web/Proyecto%201%20-%20Knapsack.zip