#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

//Prototypes
void printTable(vector<int> benefits,vector<int> table,int r,int index);

class Chromosome
{

public:
    vector<int> bits;
    int benefit;
    int weight;
    int size;

    Chromosome(){}
    Chromosome(int length)
    {
        size = length;
    }
    int getBenefit()
    {
        return benefit;
    }
    void setBenefit(int b)
    {
        benefit = b;
    }
    int getSize(){return size;}
    void setWeight(int w){weight = w;}
    int getWeight(){return weight;}
    void setBits(vector<int> v)
    {
        for(int i = 0 ; i < size; i++)
            bits[i] = v[i];
    }
    vector<int> getBits(){return bits;}
    void fill()
    {
        bits.clear();
        cout << "Enter Bits Of  Chromosome" << endl;
        for(int i = 0; i < size; i++)
        {
            int num;
            cin >> num;
            bits.push_back(num);
        }
    }
    void randomFill()
    {
        for(int i = 0; i < size; i++)
            bits.push_back(rand()%2);

    }
    void reRandomFill()
    {
        for(int i = 0; i < size; i++)
            bits[i]=(rand()%2);
    }
    void printBits()
    {
        for(int i = 0; i < bits.size(); i++)
            cout << bits[i];
    }
    void printFullChromosome()
    {
        for(int i = 0; i < bits.size(); i++)
            cout << bits[i];
        cout << endl;
        cout << "Weight " << weight << endl;
        cout << "Benefit " << benefit << endl;
    }
    bool checkIfValid(vector<int> weights, vector<int> benefits, int maxWeight)
    {
        int totalWeight =0, totalBenefit =0;

        for(int i = 0 ; i < size ; i++)
        {
            if(bits[i] == 1)
            {
                totalWeight+= weights[i];
                totalBenefit+= benefits[i];
            }
        }
        if(totalWeight > maxWeight)
            return false;
        //
        weight = totalWeight;
        benefit = totalBenefit;
        return true;
    }
    Chromosome setChromosome(Chromosome c)
    {
        (*this).setBenefit(c.getBenefit());
        (*this).setBits(c.getBits());
        (*this).setWeight(c.getWeight());
    }
};

//--------------------------------------------------------------------//
vector<int> createCumulativeTable(vector<int> benefits, vector<Chromosome> population)
{
    vector<int> CumBenefits;
    int temp;

    CumBenefits.push_back(population[0].getBenefit());

    temp = CumBenefits[0];

    for(int i=1; i < population.size(); i++)
    {
        CumBenefits.push_back(population[i].getBenefit() + temp);

        temp = CumBenefits[i];

    }
    cout<<"return"<<endl;
    return CumBenefits;
}
//--------------------------------------------------------------------//
void printTable(vector<Chromosome> population,vector<int> cumTable)
{
    system("CLS");
    for(int i = 0; i < population.size(); i++)
    {
        cout << "[" ;
        population[i].printBits();
        cout << "]      " << population[i].getBenefit() << "\t|" << "\t" << cumTable[i] << endl;
    }
    cout << endl;

    //cout << "Random number: " << r << "\nExist in index " << index << endl;
}
//--------------------------------------------------------------------//
void mutation (Chromosome ch,int maxWeight,vector<int> weights, vector<int> benefits)
{
    double pm= 0.1,r;

    r = (rand()%10 + 1.0)/10.0;

    if (r<=pm)
    {

        Chromosome child;

        child.size = ch.size;

        for(int k = 0; k < ch.size; k++)
        {
            child.bits.push_back(ch.bits[k]);
        }

        child.benefit = ch.benefit;
        child.weight = ch.weight;



        r = rand()%ch.size;

        child.bits[r]=!child.bits[r];

        if(child.checkIfValid(weights,benefits,maxWeight))
        {
            if(child.getBenefit() > ch.getBenefit())
            {
                ch.bits[r]=!ch.bits[r];
                ch.checkIfValid(weights,benefits,maxWeight);
            }

        }


    }

}
//--------------------------------------------------------------------//
void crossOver(vector<Chromosome> ch,vector<int> Choosen,int maxWeight,
               Chromosome bestSoFar,vector<int> weights, vector<int> benefits)
{
    Chromosome ch1,ch2;
    vector<int> ChoosenVector;
    int S = ch[0].size;

    int splitSize = rand()%ch[0].size;

    while(splitSize == 0 || splitSize == ch[0].size)
        splitSize = rand()%ch[0].size;

    for(int i = 0; i < Choosen.size(); i++)
    {
        ChoosenVector.push_back(Choosen[i]);
    }

    //cout << "splitSize : " << splitSize << endl;

    for(int i = ChoosenVector.size()/2; i > 0 && !ChoosenVector.empty(); i--)
    {
        ch1.bits.clear();
        ch2.bits.clear();

        int r = rand()%ChoosenVector.size();
        int r2 = rand()%ChoosenVector.size();

        while(r2 == r)
            r2 = rand()%ChoosenVector.size();


        for(int k = 0; k < splitSize; k++)
        {
            ch1.bits.push_back(ch[r].bits[k]) ;
            ch2.bits.push_back(ch[r2].bits[k]) ;
        }

        for(int k = splitSize; k < ch[0].size; k++)
        {
            ch1.bits.push_back(ch[r2].bits[k]);
            ch2.bits.push_back(ch[r].bits[k]);
        }

        ch1.size = ch[0].size;
        ch2.size = ch[0].size;

//        cout << "-------------------------" << endl;
//        cout << "r : " << r <<endl;
//        cout << "r2 : " << r2 << endl;
//
//        ch[r].printFullChromosome();
//        ch[r2].printFullChromosome();

        if(ch1.checkIfValid(weights,benefits,maxWeight))
        {
            if( bestSoFar.getBenefit() < ch1.getBenefit())
                {
                    ch[r].bits.clear();

                for(int k = 0; k < S; k++)
                    ch[r].bits.push_back(ch1.bits[k]);

                ch[r].weight = ch1.weight;
                ch[r].benefit = ch1.benefit;

                //bestSoFar.setBenefit(ch1.getBenefit());
                }
                else
                    mutation(ch[r],maxWeight,weights,benefits);

            if(ch2.checkIfValid(weights,benefits,maxWeight))
                {

                    ch[r2].bits.clear();

                    for(int k = 0; k < S; k++)
                        ch[r2].bits.push_back(ch2.bits[k]);

                    ch[r2].weight = ch2.weight;
                    ch[r2].benefit = ch2.benefit;

                    //bestSoFar.setBenefit(ch1.getBenefit());

                    mutation(ch[r2],maxWeight,weights,benefits);

                if(ch1.getBenefit() > ch2.getBenefit())
                    bestSoFar.setBenefit(ch1.getBenefit());
                else
                    bestSoFar.setBenefit(ch2.getBenefit());

                }
                else
                    bestSoFar.setBenefit(ch1.getBenefit());




        }

        else if(ch2.checkIfValid(weights,benefits,maxWeight))
        {
                ch[r2].bits.clear();

                for(int k = 0; k < S; k++)
                    ch[r2].bits.push_back(ch2.bits[k]);

                ch[r2].weight = ch2.weight;
                ch[r2].benefit = ch2.benefit;

                bestSoFar.setBenefit(ch2.getBenefit());

                mutation(ch[r2],maxWeight,weights,benefits);
        }

//        ch[r].printFullChromosome();
//        ch[r2].printFullChromosome();

//        for(int q = 0; q < ChoosenVector.size(); q++)
//        {
//            cout << ChoosenVector[q] << ",";
//        }

//        cout << endl;
//        cout << "r : "<< r <<endl;
//        cout << "r2 : "<< r2 <<endl;
//        cout << "size : "<< ChoosenVector.size() <<endl;

//        int q1 = ChoosenVector.begin() + r ;
//        int q2 = ChoosenVector.begin() + r2 ;
//        cout << ChoosenVector.begin() + r <<endl;
//        cout << ChoosenVector.begin() + r2 <<endl;
//        ChoosenVector.erase(ChoosenVector.begin() + r);
//        ChoosenVector.erase(ChoosenVector.begin() + r2);
//
//        for(int q = 0; q < ChoosenVector.size(); q++)
//        {
//            cout << ChoosenVector[q] << "," ;
//        }
//        cout << endl;

    }


}
//--------------------------------------------------------------------//
Chromosome compute(int popSize, int chSize,
                   vector<int> weights, vector<int> benefits, int maxWeight,
                   int numOfIterations, Chromosome bestSoln)
{
    //First we generate random solutions of size m
    vector<Chromosome> population;
    Chromosome bestSoFar(chSize);
    for(int i = 0; i < popSize; i++)
    {
        Chromosome c(chSize);
        c.randomFill();
        //Making sure of no invalid solution
        while( !c.checkIfValid(weights,benefits,maxWeight) )
            c.reRandomFill();
        //Keep our best
        if(i == 0)
            bestSoFar=c;
        else if(bestSoFar.getBenefit() < c.getBenefit() )
            bestSoFar.setChromosome(c);
        population.push_back(c);
    }
    vector<int> cumTable = createCumulativeTable(benefits,population);

    //Using Elitism Algorithm, we choose only some fraction of the population to change(not all the population).
    //Let it be 40% of the population
    int chosenChromosomes = (popSize*40)/100;
    vector<int> indices;


    int counter = 0;
    while(counter < numOfIterations)
    {
        for(int i = 0; i < chosenChromosomes; i++)
        {
            int r = rand()%cumTable.back();

            int index = 0;
            for(int k = cumTable.size()-1 ; k > 0; k--)
                if( r < cumTable[k] && r >= cumTable[k-1])
                {
                    index = k;
                    break;
                }

            indices.push_back(index);
        }

        sort( indices.begin(), indices.end() );
        indices.erase( unique( indices.begin(), indices.end() ), indices.end() );

        double r = (rand()%10 + 1.0)/10.0;

        if(r <= 0.7)
            crossOver(population,indices,maxWeight,bestSoFar,weights,benefits);

        if(bestSoFar.getBenefit() >= bestSoln.getBenefit())
            counter++;

    }
    cout << "Computation finished at iteration : " << counter+1 << endl;
    cout << "With best solution entered : ";
    bestSoln.printFullChromosome();
    cout << endl << "And best solution the algorithm reached : ";
    bestSoFar.printFullChromosome();
    cout << endl;
    return bestSoFar;
}
//--------------------------------------------------------------------//
int main()
{
    srand(time(0));

    int chSize;
    cout << "Enter Size of the chromosome : ";
    cin >> chSize;

    int popSize;
    cout << "Enter Size of the population : " ;
    cin >> popSize;


    int maxWeight;
    cout << "Enter Knapsack Maximum Weight of the problem : " ;
    cin >> maxWeight;

    int numOfIterations;
    cout << "Enter Knapsack Maximum number of iterations of the problem : ";
    cin >> numOfIterations;
    cout << endl;

    vector<int> benefits;
    cout << "Enter Benefits" << endl;
    for(int i = 0; i < chSize; i++)
    {
        int num;
        cin >> num;
        benefits.push_back(num);
    }
    vector<int> weights;
    cout << "Enter Weights" << endl;
    for(int i = 0; i < chSize; i++)
    {
        int num;
        cin >> num;
        weights.push_back(num);
    }

    Chromosome bestSoln(chSize);
    bestSoln.fill();
    while( !bestSoln.checkIfValid(weights,benefits,maxWeight) )
    {
        cout << "Invalid Solution.., Please Re-enter" ;

        bestSoln.fill();
    }
    //bestSoln.printBits();


    compute(popSize,chSize,weights,benefits,maxWeight,numOfIterations,bestSoln);
    return 0;
}