Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <stdio.h>
- #include <fstream>
- using namespace std;
- int cantidad_objetos,cantidad_mochilas;
- typedef struct
- {
- int espacio_objeto_a,beneficio;
- }Dato;
- vector< vector< Dato > > objetos;
- vector<int> opciones;
- int main()
- {
- int espacio_disponible_b,espacio_objeto_a,cero;//cantidad d eproblemas
- ifstream entrada;
- Dato datos;
- srand(time(NULL));
- entrada.open("ORYxZ.dat");
- //entrada.open("input.in");
- entrada>>cantidad_objetos>>cantidad_mochilas>>cero;
- objetos.resize(cantidad_mochilas);
- vector<int> guarda_beneficios(cantidad_objetos),capacidad_mochilas(cantidad_mochilas);
- for (int j = 0; j < cantidad_objetos; ++j)
- {
- entrada>>guarda_beneficios[j];
- opciones.push_back(j);
- }
- for (int i = 0; i < cantidad_mochilas; ++i)
- {
- objetos[i].resize(cantidad_objetos);
- for (int j = 0; j < cantidad_objetos; ++j)
- {
- entrada>>objetos[i][j].espacio_objeto_a;
- objetos[i][j].beneficio=guarda_beneficios[j];
- }
- }
- for (int i = 0; i < cantidad_mochilas; ++i)
- entrada>>capacidad_mochilas[i];
- cout<<"cantidad_objetos:"<<cantidad_objetos<<" cantidad_mochilas:"<<cantidad_mochilas<<endl;
- int cantidad_iteraciones=1000,mejor_beneficio=0;
- while(cantidad_iteraciones--)
- {
- int beneficio_total=0,decision;
- vector<int> opciones_restantes=opciones,espacio_total(cantidad_mochilas,0);
- for (int j = 0; j < objetos[0].size(); ++j)//voy seleccionando
- {
- bool es_candidato=true;
- decision=rand()%opciones_restantes.size();
- for (int i = 0; i < objetos.size(); ++i)
- 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
- {
- es_candidato=false;
- break;
- }
- if(es_candidato)
- {
- for (int i = 0; i < cantidad_mochilas; ++i)
- espacio_total[i]+=objetos[i][opciones_restantes[decision]].espacio_objeto_a;
- beneficio_total+=objetos[0][opciones_restantes[decision]].beneficio;
- }
- opciones_restantes.erase(opciones_restantes.begin()+decision);
- }
- if(beneficio_total>mejor_beneficio)
- mejor_beneficio=beneficio_total;
- }
- cout<<"mejor_beneficio:"<<mejor_beneficio<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement