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

3.1 - Maquina de turing que resta 1 en binario

Maquina de turing que resta 1

ΡЄΚ	σЄ∑	ℓ(Ρ,σ)
s	►	s,►,->
s	0	s,0,->
s	1	q,1,->
s	|_|	r,|_|,<-
q	0	q,0,->
q	1	q,1,->
q	|_|	t,|_|,<-
t	0	t,-1,-
r	0	r,1,<-
r	1	r,0,-

2.4 - Resta Binaria

Aquí otro ejemplo con la misma mecanica que la suma binaria pero aplicada a la resta.

------------------------------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <algorithm>

int mayor[25];
int menor[25];

//Nota: El std:: significa que usamos algun elemento de la biblioteca estandar

void convierte(unsigned long n1, unsigned long n2){
    std::string binario;                                //Definimos string del resultado
    int c=0;
    for(unsigned long i=n1,j=n2;i!=0 || j!=0;i/=2,j/=2){
        if(n1 >= n2){                                    //Acomodamos el mayor - menor para que no quede resta negativa
            if(i % 2 != 0){
                mayor[c] = 1;
            }else{
                mayor[c] = 0;
            }
           
            if(j % 2 != 0){
                menor[c] = 1;
            }else{
                menor[c] = 0;
            }
        }else{
            if(i % 2 != 0){
                menor[c] = 1;
            }else{
                menor[c] = 0;
            }
           
            if(j % 2 != 0){
                mayor[c] = 1;
            }else{
                mayor[c] = 0;
            }
        }
        c++;
    }
   
    for(int i=0;i<25;i++){
        if((mayor[i]-menor[i]) < 0){                    //Acomodamos el algoritmo como cualquier resta
            mayor[i+1] -= 1;
            mayor[i] += 2;                                //Como el sistema es binario aumentamos 2
            std::cout << 'h';
        }

        binario.push_back('0' + (mayor[i]-menor[i]));    //Asignamos en la cadena el resultado
        mayor[i] = 0;                                    //Reiniciamos los valores
        menor[i] = 0;
    }
  
    std::reverse(binario.begin(),binario.end());        //Como push_back lo inserta adelante de la cadena, lo invertimos
   
    if(binario.empty()){
            binario.push_back('0');                        //Si nos dieron 0 les davolemos 0
    }
      
       std::cout <<"Resta: " << binario <<"\n\n\n";
}

int main(){
    unsigned long n1,n2;
    while(std::cin>>n1>>n2){                            //Ciclo los valores decimales
        convierte(n1,n2);
    }
  
    return 0;
}

2.3 - Suma Binaria

Aquí una forma para simular la suma binaria, me salio algo largo el código, después tratare de mejorarlo un poco, uso un algoritmo simple de suma sobre la base del sistema en este caso binario.

----------------------------------------------------------------------------------------------------

#include <iostream>
#include <string>
#include <algorithm>

bool decimal1[25];
bool decimal2[25];

//Nota: El std:: significa que usamos algun elemento de la biblioteca estandar

void convierte(unsigned long n1, unsigned long n2){
    std::string binario;
    int c=0,acomulado=0;
    for(unsigned long i=n1,j=n2;i!=0 || j!=0;i/=2,j/=2){    //Calculamos los numeros binarios
        if(i % 2 != 0){
            decimal1[c] = 1;
        }else{
            decimal1[c] = 0;
        }
       
        if(j % 2 != 0){
            decimal2[c] = 1;
        }else{
            decimal2[c] = 0;
        }
        c++;
    }

    for(int i=0;i<25;i++){
        binario.push_back('0' + ((decimal1[i]+decimal2[i]+acomulado) % 2)); //Calculamos el resultado del digito
        acomulado = (decimal1[i]+decimal2[i]+acomulado)/2;    //Acomulamos si sobrepaso la base
        decimal1[i]=0;                                        //Reiniciamos los valores
        decimal2[i]=0;
    }
  
    std::reverse(binario.begin(),binario.end());            //Como push_back lo inserta adelante de la cadena, lo invertimos
   
    if(binario.empty()){
        binario.push_back('0');                                //Si nos dieron 0 les davolemos 0
    }
      
       std::cout <<"Suma: " << binario <<"\n\n\n";                //Resultado
}

int main(){
    unsigned long n1,n2;
    while(std::cin>>n1>>n2){                                //Ciclo pidiendo los valores decimales
        convierte(n1,n2);
    }
  
    return 0;
}