#include <iostream>
#include <bitset>
#include <limits>
#include <cmath>
#include <ctime>
#include <algorithm>

using namespace std;

const int NUMBITS = 500;
const double PESOMAX = 25;
const double penalidade = 20;
/*const int NUMBITS = 5;
const double PESOMAX = 13;
const double penalidade = 20;*/

double pesos[NUMBITS];
double utilidades[NUMBITS];
/*double pesos []      = {1, 6, 4, 3, 3};
double utilidades [] = {6, 10, 9, 4, 2};*/

void gerarAleatoriamente(){
    for (int i = 0; i < NUMBITS; i++) {
        utilidades[i] = rand()%20;
        pesos[i] = rand()%20;
    }
}

/* Function to print an array */
void printArray(double arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%2.f ", arr[i]);
    printf("\n");
}

// Funcao q realiza as trocas
void swap(double *xp, double *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void bubbleSort(double arr[], int n, double util[])
{
   int i, j;
   for (i = 0; i < n-1; i++)
   {
     for (j = 0; j < n-i-1; j++)
     {
        if (util[j] < util[j+1])
        {
           swap(&util[j], &util[j+1]);
           swap(&arr[j], &arr[j+1]);
        }
     }
   }
}

double fObj(bitset<NUMBITS> solucao) {
    double somautil=0, somapeso=0;
    for(int i=0; i<NUMBITS; i++) {
        somapeso += pesos[i] * solucao[i];
        somautil += utilidades[i] * solucao[i];
    }
    if ( somapeso > PESOMAX ) {
        somautil -= (somapeso-PESOMAX) * penalidade;
    }
    return somautil;
}

bitset<NUMBITS> buscaLocal(bitset<NUMBITS> sIni) {

    bitset<NUMBITS> solucao, solucaoAux;

    solucao = sIni ;
    int cont=0;
    bool melhorou;
    do {
        melhorou = false;
        for(int i=0; i<NUMBITS; i++) {
            solucaoAux = solucao;
            solucaoAux[i] = ~solucaoAux[i];
            double fsolucao, fsolucaoAux;
            fsolucao = fObj(solucao);
            fsolucaoAux = fObj(solucaoAux);

            if ( fsolucaoAux > fsolucao ) {
                solucao = solucaoAux;
                melhorou = true;
            }
            //cout << ++cont << "\t" << fsolucao << endl;
            cout << ++cont << "\t" << fsolucao << "\t" << fsolucaoAux << endl;
        }
    } while (melhorou);
    return solucao;
}

bitset<NUMBITS> obtemSolucaoInicial() {
    int sIni [] = {0,1,0,1,1};
    bitset<NUMBITS> solInicial;

    for(int i=0; i<NUMBITS; i++) {
        solInicial[i] = rand()%2;  // solução aletória
        //solInicial[i] = sIni[i]; // solução a partir do vetor sIni [] = {0,1,0,1,1}
    }
    return solInicial;
}

bitset<NUMBITS> obtemSolucaoInicialGuloso(double peso[]) {
    bitset<NUMBITS> solInicial;
    double pesoFinal = 0;
    double vetor[NUMBITS];
    for(int i = 0; i < NUMBITS; i++) {
        if(pesoFinal + peso[i] <= PESOMAX) {
            pesoFinal += peso[i];
            vetor[i] = 1;
        } else {
            vetor[i] = 0;
        }
    }
    printArray(vetor, NUMBITS);

    for(int i=0; i<NUMBITS; i++) {
        solInicial[i] = vetor[i];
    }
    return solInicial;
}

int main() {
    srand(time(NULL));
    gerarAleatoriamente();

    printArray(utilidades, NUMBITS);
    printArray(pesos, NUMBITS);
    cout<<"\n";

    bubbleSort(pesos, NUMBITS, utilidades);

    bitset<NUMBITS> solInicial = obtemSolucaoInicialGuloso(pesos);
    bitset<NUMBITS> s = buscaLocal(solInicial);

    // código para inverter o bitset (little-endian  => big-endian)
    string s_ini_str=solInicial.to_string();
    reverse(s_ini_str.begin(), s_ini_str.end());
    string s_fin_str=s.to_string();
    reverse(s_fin_str.begin(), s_fin_str.end());

    cout << "fObj inicial =\t" << fObj(solInicial) << " para s =\t" << s_fin_str << endl;
    cout << "fObj máximo =\t" << fObj(s) << " para s =\t" << s_ini_str << endl;
}