Advertisement
Gustavo_Inzunza

Mochila Metaheuirístico

Jul 12th, 2013
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5. #include <stdio.h>
  6. #include <fstream>
  7. using namespace std;
  8. int cantidad_objetos,cantidad_mochilas;
  9. typedef struct
  10. {
  11.     int espacio_objeto_a,beneficio;
  12. }Dato;
  13. vector< vector< Dato > > objetos;
  14. vector<int> opciones;
  15. int main()
  16. {
  17.     int espacio_disponible_b,espacio_objeto_a,cero;//cantidad d eproblemas
  18.     ifstream entrada;
  19.     Dato datos;
  20.     srand(time(NULL));
  21.     entrada.open("ORYxZ.dat");
  22.     //entrada.open("input.in");
  23.     entrada>>cantidad_objetos>>cantidad_mochilas>>cero;
  24.     objetos.resize(cantidad_mochilas);
  25.     vector<int> guarda_beneficios(cantidad_objetos),capacidad_mochilas(cantidad_mochilas);
  26.     for (int j = 0; j < cantidad_objetos; ++j)
  27.     {
  28.         entrada>>guarda_beneficios[j];
  29.         opciones.push_back(j);
  30.     }
  31.     for (int i = 0; i < cantidad_mochilas; ++i)
  32.     {
  33.         objetos[i].resize(cantidad_objetos);
  34.         for (int j = 0; j < cantidad_objetos; ++j)
  35.         {
  36.             entrada>>objetos[i][j].espacio_objeto_a;
  37.             objetos[i][j].beneficio=guarda_beneficios[j];
  38.         }
  39.     }
  40.     for (int i = 0; i < cantidad_mochilas; ++i)
  41.         entrada>>capacidad_mochilas[i];
  42.     cout<<"cantidad_objetos:"<<cantidad_objetos<<" cantidad_mochilas:"<<cantidad_mochilas<<endl;
  43.     int cantidad_iteraciones=1000,mejor_beneficio=0;
  44.     while(cantidad_iteraciones--)
  45.     {
  46.         int beneficio_total=0,decision;
  47.         vector<int> opciones_restantes=opciones,espacio_total(cantidad_mochilas,0);
  48.         for (int j = 0; j < objetos[0].size(); ++j)//voy seleccionando
  49.         {
  50.             bool es_candidato=true;
  51.             decision=rand()%opciones_restantes.size();
  52.             for (int i = 0; i < objetos.size(); ++i)
  53.                 if(espacio_total[i]+objetos[i][opciones_restantes[decision]].espacio_objeto_a>capacidad_mochilas[i])//veo que mi selección no se sobrepase con el espacio de la mochila
  54.                 {
  55.                     es_candidato=false;
  56.                     break;             
  57.                 }
  58.             if(es_candidato)
  59.             {
  60.                 for (int i = 0; i < cantidad_mochilas; ++i)
  61.                     espacio_total[i]+=objetos[i][opciones_restantes[decision]].espacio_objeto_a;
  62.                 beneficio_total+=objetos[0][opciones_restantes[decision]].beneficio;
  63.             }
  64.             opciones_restantes.erase(opciones_restantes.begin()+decision);
  65.         }
  66.         if(beneficio_total>mejor_beneficio)
  67.             mejor_beneficio=beneficio_total;
  68.     }
  69.     cout<<"mejor_beneficio:"<<mejor_beneficio<<endl;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement